Simultaneous Embedding of Planar Graphs with Few Bends

Erten, Cesim and Kobourov, Stephen G. (2004) Simultaneous Embedding of Planar Graphs with Few Bends. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 195-205 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_21).

Full text not available from this repository.

Abstract

We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n^2)× O(n^2) grid, with at most three bends per edge, where n is the number of vertices. For the case when the input graphs are both trees, only one bend per edge is required. We also describe an O(n) time algorithm for simultaneous embedding with fixed-edges for tree-path pairs on the O(n)× O(n^2) grid with at most one bend per tree-edge and no bends along path edges. This work is partially supported by the NSF under grant ACR-0222920 and by ITCDI under grant 003297.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_21
Classifications:M Methods > M.900 Tree
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.210 Bends
ID Code:587

Repository Staff Only: item control page

References

U. Brandes and S. R. Corman. Visual unrolling of network evolution and the analysis of dynamic discourse. In IEEE Symposium on Information Visualization (INFOVIS '02), pages 145-151, 2002.

P. Brass, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kouborov, A. Lubiw, and J. S. B. Mitchell. On simultaneous graph embedding. In 8th Workshop on Algorithms and Data Structures, pages 243-255, 2003.

N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14:210-223, 1985.

N. Chiba and T. Nishizeki. The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. Journal of Algorithms, 10(2):187-211, 1989.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41-51, 1990.

M. B. Dillencourt, D. Eppstein, and D.S. Hirschberg. Geometric thickness of complete graphs. Journal of Graph Algorithms and Applications, 4(3):5-17, 2000.

C. A. Duncan, D. Eppstein, and S. G. Kobourov. The geometric thickness of low degree graphs. In 20th Annual ACM-SIAM Symposium on Computational Geometry (SCG), pages 340-346, 2004.

CD. Erten, S. G. Kobourov, A. Navabia, and V. Le. Simultaneous graph drawing: Layout algorithms and visualization schemes. In 11th Symposium on Graph Drawing (GD), pages 437-449, 2003.

I. Fáry. On straight lines representation of planar graphs. Acta Scientiarum Mathematicarum, 11:229-233, 1948.

J. Hopcraft and R. E. Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549-568, 1974.

M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.

P. Mutzel, T. Odenthal, and M. Scharbrodt. The thickness of graphs: a survey. Graphs Combin., 14(1):59-73, 1998.

J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics, 17:717-728, 2001.

W. Schnyder. Embedding planar graphs on the grid. In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 138-148, 1990.

S. K. Stein. Convex maps. Proceedings of the American Mathematical Society, 2(3):464-466, 1951.

W. T. Tutte. How to draw a graph. Proc. London Math. Society, 13(52):743-768, 1963.

K. Wagner. Bemerkungen zum vierfarbenproblem. Jahresbericht der Deutschen Mathematicer-Vereinigung, 46:26-32, 1936.