Width-optimal visibility representations of plane graphs

Jia Hao Fan*, Chun-Cheng Lin, Hsueh I. Lu, Hsu Chun Yen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Scopus citations

Abstract

Given an n-node plane graph G, the visibility representation of G is concerned with drawing each node of G using a horizontal line segment such that the line segments associated with any two adjacent nodes of G are vertically visible to each other. Finding most compact visibility representations of plane graphs is not only of theoretical importance but also of practical interest, and has received much attention in the community of algorithmic graph theory. In this paper, we give a linear-time algorithm to find a visibility representation of G no wider than [4n/3] - 2. Our result improves upon the previously known upper bound 4n/3 + 2[√n], providing a positive answer to a conjecture suggested in the literature about whether an upper bound 4n/3 + O(1) on the required width can be achieved for an arbitrary plane graph. In fact, our visibility representation achieves optimality in the upper bound of width because the bound differs from the previously known lower bound [4n/3] - 3 only by one unit.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings
Pages160-171
Number of pages12
DOIs
StatePublished - Dec 2007
Event18th International Symposium on Algorithms and Computation, ISAAC 2007 - Sendai, Japan
Duration: 17 Dec 200719 Dec 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4835 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Symposium on Algorithms and Computation, ISAAC 2007
Country/TerritoryJapan
CitySendai
Period17/12/0719/12/07

Fingerprint

Dive into the research topics of 'Width-optimal visibility representations of plane graphs'. Together they form a unique fingerprint.

Cite this