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 , pp. 262-272(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_27).

Full text not available from this repository.

Abstract

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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/593

Actions (login required)

View Item View Item