An application of well-orderly trees in graph drawing

Huaming Zhang; H. E. Xin

doi:10.1142/S0129054106004303

An application of well-orderly trees in graph drawing

Huaming Zhang
, H. E. Xin

Department of Computer Science and Engineering

University of Alabama in Huntsville

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height ≤ [4n-1/5], which can be constructed in linear time. This improves the best previous bound of ≤ [5n/6]

Original language	English
Pages (from-to)	1129-1141
Number of pages	13
Journal	International Journal of Foundations of Computer Science
Volume	17
Issue number	5
DOIs	https://doi.org/10.1142/S0129054106004303
State	Published - Oct 2006

Keywords

Plane graph
Plane triangulation
Visibility representation
Well orderly tree

Access to Document

10.1142/S0129054106004303

Cite this

@article{a0faf1ba37794415900203bb7e013dac,

title = "An application of well-orderly trees in graph drawing",

abstract = "Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height ≤ [4n-1/5], which can be constructed in linear time. This improves the best previous bound of ≤ [5n/6]",

keywords = "Plane graph, Plane triangulation, Visibility representation, Well orderly tree",

author = "Huaming Zhang and Xin, \{H. E.\}",

year = "2006",

month = oct,

doi = "10.1142/S0129054106004303",

language = "English",

volume = "17",

pages = "1129--1141",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "5",

}

TY - JOUR

T1 - An application of well-orderly trees in graph drawing

AU - Zhang, Huaming

AU - Xin, H. E.

PY - 2006/10

Y1 - 2006/10

N2 - Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height ≤ [4n-1/5], which can be constructed in linear time. This improves the best previous bound of ≤ [5n/6]

AB - Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height ≤ [4n-1/5], which can be constructed in linear time. This improves the best previous bound of ≤ [5n/6]

KW - Plane graph

KW - Plane triangulation

KW - Visibility representation

KW - Well orderly tree

UR - https://www.scopus.com/pages/publications/33748801189

U2 - 10.1142/S0129054106004303

DO - 10.1142/S0129054106004303

M3 - Article

AN - SCOPUS:33748801189

SN - 0129-0541

VL - 17

SP - 1129

EP - 1141

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 5

ER -

An application of well-orderly trees in graph drawing

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this