Logo

Login

Simultaneous Embedding of Planar Graphs with Few Bends

Erten, Cesim and Kobourov, Stephen G. (2004) Simultaneous Embedding of Planar Graphs with Few Bends. [Conference Paper]

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
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
Deposited By:Selbach, Anna
Deposited On:19 Jul 2005
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=195

Repository Staff Only: item control page

References

1. 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.

2. 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.

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

4. 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.

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

6. 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.

7. 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.

8. 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.

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

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

11. 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.

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

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

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.