creators_name: Kaufmann, Michael
creators_name: Vrto, Imrich
creators_name: Geyer, Markus
editors_name: Healy, Patrick
editors_name: Nikolov, Nikola S.
editors_id: Healy, Patrick
editors_id: Nikolov, Nikola S.
type: confpaper
datestamp: 2006-02-22
lastmod: 2008-09-18 11:08:59
metadata_visibility: show
title: Two trees which are self-intersecting when drawn simultaneously
ispublished: pub
subjects: Z.500
subjects: M.900
subjects: P.720
subjects: G.490
subjects: G.560
full_text_status: none
abstract: An actual topic in the graph drawing is the question how to draw two edge sets on the same vertex set, the so-called simultaneous drawing of graphs. The goal is to simultaneously find a nice drawing for both of the sets. It has been found out that only restricted classes of planar graphs can be drawn simultaneously using straight lines and without crossings within the same edge set. In this paper, we negatively answer one of the most often posted open questions namely whether any two trees with the same vertex set can be drawn simultaneously crossing-free in a straight line way.
    
date: 2006
date_type: published
publisher: Springer
pagerange: 201-210
refereed: FALSE
referencetext: Brass, P., Cenek, E., Duncan, A., Efrat, A., Erten, C, Ismailescu, D., Kobourov, S., Lubiw, A., Mitchell, J.S.B.: On Simultaneous Planar Graph Embeddings. Dehne F., Sack, J., Snid, M. (eds.): Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol.  2748. Springer, Berlin (2002) 243-255

Duncan, C.A., Eppstein, D., Kobourov, S.G.: The Geometric Thickness of Low Degree Graphs. In: Boissonant, J.-D., Snoeyink, J. (eds.): 23rd Annual Symp. on Computational geometry. ACM Press, New York (2004) 340-346 

Erten, C.,  Kobourov, S.G.: Simultaneous Embedding of a Planar Graph and its Dual on the Grid. Bose, P., Morin, P. (eds.): 13th Intl. Symp. on Algorithms & Computation. Lecture Notes in Computer Science, Vol.  2518. Springer, Berlin (2002) 575-587

Erten, C.,  Kobourov, S.G.,   Le, V.,  Navabi, A.: Simultaneous Graph Drawing: Layout Algorithms and Visualization Schemes. Liotta, G. (ed.): 11th Intl.  Symp. on Graph Drawing. Lecture Notes in Computer Science, Vol. 2912. Springer, Berlin (2003) 437-449

Erten, C., Kobourov, S.G.: Simultaneous Embedding of Planar Graphs with Few  Bends. Pach, J. (ed.): 12th Intl. Symp.  on Graph Drawing. Lecture Notes in Computer Science, Vol. 3383. Springer, Berlin (2004) 195-205

Kobourov, S.G.,  Pitta, C.: An Interactive Multi-User System for Simultaneous  Graph Drawing. Pach, J. (ed.): 12th Intl.  Symposium on Graph Drawing. Lecture Notes in Computer Science, Vol. 3383. Springer, Berlin (2004) 492-501


citation: Kaufmann, Michael and Vrto, Imrich and Geyer, Markus (2006) Two trees which are self-intersecting when drawn simultaneously. [Conference Paper]