@inproceedings{1749204bdc7045c798432008ce236abf,
title = "Nearly optimal visibility representations of plane graphs",
abstract = "The visibility representation (VR for short) is a classical representation of plane graphs. VR has various applications and has been extensively studied in literature. One of the main focuses of the study is to minimize the size of VR. It is known that there exists a plane graph G with n vertices where any VR of G requires a size at least ([2n/3] × ([4n/3] - 3). In this paper, we prove that every plane graph has a VR with height at most 2n/3 + 2[√n/2], and a VR with width at most 4n/3 + 2[√n]. These representations are nearly optimal in the sense that they differ from the lower bounds only by a lower order additive term. Both representations can be constructed in linear time. However, the problem of finding VR with optimal height and optimal width simultaneously remains open.",
author = "Xin He and Huaming Zhang",
year = "2006",
doi = "10.1007/11786986\_36",
language = "English",
isbn = "3540359044",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "407--418",
booktitle = "Automata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Proceedings",
address = "Germany",
note = "33rd International Colloquium on Automata, Languages and Programming, ICALP 2006 ; Conference date: 10-07-2006 Through 14-07-2006",
}