In this paper, we study k-spine, h-bend planar drawings in which each vertex of a planar graph G lies on one of k $\geq$ 1 horizontal lines and each edge of G is drawn as a polyline containing at most h $\geq$ 0 bends. A graph with a k-spine, h-bend planar drawing is said to be k-spine, h-bend planar. We mainly focus on k-spine, 1-bend planar drawings, showing that for each k $\geq$ 2, there exists a planar graph that is not k-spine, 1-bend planar, and furthermore, that it is NP-hard to test k-spine, 1-bend planarity. Given this complexity result, we further narrow our focus onto 2-spine, 1-bend planar drawings. We characterize 2-spine, 1-bend planarity using a new generalization of Hamiltonian graphs that we call Hamiltonian-with-handles graphs. We observe that our characterization naturally extends the connection between 2-page book embeddings and Hamiltonicity. Finally, we use our characterization to show that 2-outerplanar graphs are 2-spine, 1-bend planar.

K-Spine, 1-Bend Planarity

DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;
2006

Abstract

In this paper, we study k-spine, h-bend planar drawings in which each vertex of a planar graph G lies on one of k $\geq$ 1 horizontal lines and each edge of G is drawn as a polyline containing at most h $\geq$ 0 bends. A graph with a k-spine, h-bend planar drawing is said to be k-spine, h-bend planar. We mainly focus on k-spine, 1-bend planar drawings, showing that for each k $\geq$ 2, there exists a planar graph that is not k-spine, 1-bend planar, and furthermore, that it is NP-hard to test k-spine, 1-bend planarity. Given this complexity result, we further narrow our focus onto 2-spine, 1-bend planar drawings. We characterize 2-spine, 1-bend planarity using a new generalization of Hamiltonian graphs that we call Hamiltonian-with-handles graphs. We observe that our characterization naturally extends the connection between 2-page book embeddings and Hamiltonicity. Finally, we use our characterization to show that 2-outerplanar graphs are 2-spine, 1-bend planar.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11391/121684
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact