@inbook{31675b67da8e47df96c5ef9b8b7fcf50,
title = "On visibility representation of plane graphs",
abstract = "In a visibility representation (VR for short) of a plane graph G, each vertex of G is represented by a horizontal line segment such that the line segments representing any two adjacent vertices of G are joined by a vertical line segment. Rosenstiehl and Tarjan [11], Tamassia and Tollis [14] independently gave linear time VR algorithms for 2-connected plane graph. Recently, Lin et. al. reduced the width bound to [22n-42/15] [10]. In this paper, we prove that any plane graph G has a VR with width at most [13n-24/9]. For a 4-connected plane triangulation G, we give a visibility representation of G with height at most [3n/4]. In order to show that, we first show that every such graph has a canonical ordering tree with at most [n+1/2] leaves instead of the previously known bound [2n+1/3] which is of independent interest. All of them can be obtained in linear time.",
author = "Huaming Zhang and Xin He",
year = "2004",
doi = "10.1007/978-3-540-24749-4\_42",
language = "English",
isbn = "9783540212362",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "477--488",
editor = "Volker Diekert and Michel Habib",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}