License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.141
URN: urn:nbn:de:0030-drops-30064
URL: http://drops.dagstuhl.de/opus/volltexte/2011/3006/
Go to the corresponding Portal


Wang, Jiun-Jie ; He, Xin

Compact Visibility Representation of Plane Graphs

pdf-format:
Document 1.pdf (661 KB)


Abstract

The visibility representation (VR for short) is a classical representation of plane graphs. It has various applications and has been extensively studied. A main focus of the study is to minimize the size of the VR. It is known that there exists a plane graph $G$ with $n$ vertices where any VR of $G$ requires a grid of size at least (2/3)n x((4/3)n-3) (width x height). For upper bounds, it is known that every plane graph has a VR with grid size at most (2/3)n x (2n-5), and a VR with grid size at most (n-1) x (4/3)n. It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely with size at most c_h n x c_w n with c_h < 1 and c_w < 2$). In this paper, we provide the first VR construction with this property. We prove that every plane graph of n vertices has a VR with height <= max{23/24 n + 2 Ceil(sqrt(n))+4, 11/12 n + 13} and width <= 23/12 n. The area (height x width) of our VR is larger than the area of some of previous results. However, bounding one dimension of the VR only requires finding a good st-orientation or a good dual s^*t^*-orientation of G. On the other hand, to bound both dimensions of VR simultaneously, one must find a good $st$-orientation and a good dual s^*t^*-orientation at the same time, and thus is far more challenging. Since st-orientation is a very useful concept in other applications, this result may be of independent interests.

BibTeX - Entry

@InProceedings{wang_et_al:LIPIcs:2011:3006,
  author =	{Jiun-Jie Wang and Xin He},
  title =	{{Compact Visibility Representation of Plane Graphs}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{141--152},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3006},
  URN =		{urn:nbn:de:0030-drops-30064},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2011.141},
  annote =	{Keywords: plane graph, plane triangulation, visibility representation, st-orientation}
}

Keywords: plane graph, plane triangulation, visibility representation, st-orientation
Seminar: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011


DROPS-Home | Fulltext Search | Imprint Published by LZI