An embedded planar graph G is k-spine drawable, k >= 0, if there exists an embedding-preserving 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: (1) Introduce the notion of hamiltonian-with-handles graphs and show that a planar embedded graph is 2-spine drawable if an only if it is hamiltonian-with-handles. (2) Give examples of planar graphs that are/are not 2-spine drawable and present linear-time drawing techniques. (3) Prove that deciding whether or not an embedded planar graph is 2-spine drawable is NP-Complete. (4) 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.
Hamiltonian-with-handles Graphs and the k-spine Drawability Problem
DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;
2004
Abstract
An embedded planar graph G is k-spine drawable, k >= 0, if there exists an embedding-preserving 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: (1) Introduce the notion of hamiltonian-with-handles graphs and show that a planar embedded graph is 2-spine drawable if an only if it is hamiltonian-with-handles. (2) Give examples of planar graphs that are/are not 2-spine drawable and present linear-time drawing techniques. (3) Prove that deciding whether or not an embedded planar graph is 2-spine drawable is NP-Complete. (4) 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
