In this paper we characterize the class of plane graphs that can be embedded on the two- dimensional grid with at most one bend on each edge. In addition, we provide an algorithm that either detects a forbidden configuration or generates an embedding with at most one bend on each edge.
An algorithm for 1-bend embeddings of planar graphs in the two-dimensional grid / Morgana, Maria Aurora; PICININ DE MELLO, C.; Sontacchi, Giovanna. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 141:(2004), pp. 225-241. [10.1016/s0166-218x(03)00373-1]
An algorithm for 1-bend embeddings of planar graphs in the two-dimensional grid.
MORGANA, Maria Aurora;SONTACCHI, Giovanna
2004
Abstract
In this paper we characterize the class of plane graphs that can be embedded on the two- dimensional grid with at most one bend on each edge. In addition, we provide an algorithm that either detects a forbidden configuration or generates an embedding with at most one bend on each edge.File allegati a 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.
