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 \(\lfloor\frac{4n}{3}\rfloor-2\). Our result improves upon the previously known upper bound \(\frac{4n}{3}+2\lceil \sqrt{n}\rceil\), providing a positive answer to a conjecture suggested in the literature about whether an upper bound \(\frac{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 \(\lfloor\frac{4n}{3}\rfloor-3\) only by one unit.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Di Battista, G., Tamassia, R., Tollis, I.G.: Constrained visibility representations of graphs. Inf. Process. Lett. 41(1), 1–7 (1992)
He, X., Zhang, H.: Nearly optimal visibility representations of plane graphs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 407–418. Springer, Heidelberg (2006)
Kant, G.: A more compact visibility representation. Internat. J. Comput. Geom. Appl. 7, 197–210 (1997)
Lin, C.-C., Lu, H.-I., Sun, I.-F.: Improved compact visibility representation of planar graph via Schnyder’s realizer. SIAM J. Discrete Math. 18(3), 19–29 (2004)
Nummenmaa, J.: Constructing compact rectilinear planar layouts using canonical representation of planar graphs. Theoret. Comput. Sci. 99, 213–230 (1992)
Otten, R., van Wijk, J.: Graph representations in interactive layout design. In: IEEE Internat. Sympos. on Circuits and Systems, pp. 914–918 (1978)
Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1(4), 343–353 (1986)
Schlag, M., Luccio, F., Maestrini, P., Lee, D.T., Wong, C.K.: A visibility problem in VLSI layout compaction. In: Preparata, F.P. (ed.) Advances in Computing Research, vol. II, pp. 259–282. JAI Press, Greenwich, CT (1985)
Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1, 321–341 (1986)
Zhang, H., He, X.: Compact visibility representation and straight-line grid embedding of plane graphs. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 493–504. Springer, Heidelberg (2003)
Zhang, H., He, X.: Improved visibility representation of plane graphs. Comput. Geom. 30(1), 29–39 (2005)
Zhang, H., He, X.: Visibility representation of plane graphs via canonical ordering tree. Inf. Process. Lett. 96, 41–48 (2005)
Zhang, H., He, X.: An application of well-orderly trees in graph drawing. Int. J. Found. Comput. Sci. 17(5), 1129–1142 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fan, JH., Lin, CC., Lu, HI., Yen, HC. (2007). Width-Optimal Visibility Representations of Plane Graphs. In: Tokuyama, T. (eds) Algorithms and Computation. ISAAC 2007. Lecture Notes in Computer Science, vol 4835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77120-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-77120-3_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77118-0
Online ISBN: 978-3-540-77120-3
eBook Packages: Computer ScienceComputer Science (R0)