Actas de congresos
An Algorithm For 1-bend Embeddings Of Plane Graphs In The Two-dimensional Grid
Registro en:
Discrete Applied Mathematics. , v. 141, n. 1-3, p. 225 - 241, 2004.
0166218X
10.1016/S0166-218X(03)00373-1
2-s2.0-2942541366
Autor
Morgana A.
De Mello C.P.
Sontacchi G.
Institución
Resumen
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. © 2003 Elsevier B.V. All rights reserved. 141 1-3 225 241 Liu, Y., (1995) Embeddability in Graphs, , Amsterdam: Kluwer Academic Publishers Liu, Y., Morgana, A., Simeone, B., General theoretical results on rectilinear embeddability of graphs (1991) Acta Math. Appl. Sinica, 7, pp. 187-192 Liu, Y., Morgana, A., Simeone, B., A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid (1998) Discrete Appl. Math., 81, pp. 69-91 Tarjan, R.E., Depth-first search and linear graph algorithms (1972) SIAM J. Comput., 1, pp. 146-160