Hamiltonian-with-Handles Graphs and the k-Spine Drawability Problem

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Suderman, Matthew (2004) Hamiltonian-with-Handles Graphs and the k-Spine Drawability Problem. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 262-272 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_27).

Full text not available from this repository.


A planar graph G is k-spine drawable, k >= 0, if there exists a planar drawing of G in which each vertex of G lies on one of k horizontal lines, and each edge of G is drawn as a polyline consisting of at most two line segments. In this paper we: (i) Introduce the notion of hamiltonian-with-handles graphs and show that a planar graph is 2-spine drawable if and only if it is hamiltonian-with-handles. (ii) Give examples of planar graphs that are/are not 2-spine drawable and present linear-time drawing techniques for those that are 2-spine drawable. (iii) Prove that deciding whether or not a planar graph is 2-spine drawable is NP-Complete. (iv) Extend the study to k-spine drawings for k >= 2, provide examples of non-drawable planar graphs, and show that the k-drawability problem remains NP-Complete for each fixed k >= 2. The authors would like to thank Sue Whitesides for the useful discussion about the topic of this paper. Research supported in part by ldquoProgetto ALINWEB: Algoritmica per Internet e per il Webrdquo, MIUR Programmi di Ricerca Scientifica di Rilevante Interesse Nazionale.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_27
Classifications:P Styles > P.480 Layered
G Algorithms and Complexity > G.560 Geometry
P Styles > P.540 Planar
ID Code:593

Repository Staff Only: item control page


F. Bernhart and P. Kainen. The book thickness of a graph. Journal Combinatorial Theory, Series B, 27(3):320-331, 1979.

I. Cahit and M. Ozel. The characterization of all maximal planar graphs, Manuscript. http://www. emu. edu.tr/~cahit/prprnt.html, 2003.

F. R. K. Chung, F. T. Leighton, and A. Rosenberg.Embedding graphs in books: A layout problem with applications to VLSI design. SIAM Journal on Algebraic and Discrete Methods, 8:33-58, 1987.

S. Cornelsen, T. Schank, and D. Wagner. Drawing graphs on two and three lines. In Graph Drawing (Proc. GD'02), volume 2528 of LNCS, pages 31-41. Springer-Verlag, 2002.

P. Eades, B. D. McKay, and N. C. Wormald. On an edge crossing problem. In Proc. of the 9th Austrian Computer Science Conference, ACSC9, pages 327-334, 1986.

S. Felsner, G. Liotta, and S. K. Wismath. Straight-line drawings on restricted integer grids in two and three dimensions. Journal of Graph Algorithms and Appl., 7(4):363-398, 2003.

U. Fößmeier and M. Kaufmann. Nice drawings for planar bipartite graphs. In 3rd Italian Conference on Algorithms and Complexity (Proc. CIAC'97), volume 1203 of Lecture Notes in Computer Science, pages 122-134. Springer-Verlag, 1997.

T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, 1990.

M. Suderman. Pathwidth and layered drawings of trees. Int. Journal of Comp. Geometry, 14(3):203-225, 2004.

M. S. Waterman and J. R. Griggs. Interval graphs and maps of DNA. Bulletin of Mathematical Biology, 48(2):189-195, 1986.

A. Wigderson. The complexity of the hamiltonian circuit problem for maximal planar graphs. Technical Report 298, Princeton University, EECS Department, 1982.