Embedding Graphs Simultaneously with Fixed Edges

Frati, Fabrizio (2007) Embedding Graphs Simultaneously with Fixed Edges. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 108-113 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_12).

Full text not available from this repository.


We show that a planar graph and a tree can always be simultaneously embedded with fixed edges and that two outerplanar graphs generally cannot.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_12
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.490 Embeddings
M Methods > M.700 Planarization-based
ID Code:766

Repository Staff Only: item control page


P. Brass, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. B. Mitchell. On simultaneous planar graph embeddings. In WADS, pages 243-255, 2003.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

E. Di Giacomo and G. Liotta. A note on simultaneous embedding of planar graphs (abstract). In Proc. EWCG 2005, pages 207-210, 2005.

C. Erten and S. G. Kobourov. Simultaneous embedding of planar graphs with few bends. In Graph Drawing, pages 195-205, 2004.

I. Fary. On straight line representation of planar graphs. Ac. Sci. Math. Sz., 11:229233, 1948.

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

M. Geyer, M. Kaufmann, and I. Vrto. Two trees which are self-intersecting when drawn simultaneously. In Graph Drawing, pages 201-210, 2005.

T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms. North-Holland, Amsterdam, 1988.

J. Pach and R. Wenger. Embedding planar graphs at xed vertex locations. In Graph Drawing, pages 263-274, 1998.

W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discr. Alg., pages 138-148, 1990.