We study the problem of drawing simultaneously embedded graphs with few bends. We show that for any simultaneous embedding with fixed edges (Sefe) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (Sge) for a non-trivial class of graphs.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | Drawing Simultaneously Embedded Graphs with Few Bends |
Autori: | |
Data di pubblicazione: | 2014 |
Serie: | |
Abstract: | We study the problem of drawing simultaneously embedded graphs with few bends. We show that for a...ny simultaneous embedding with fixed edges (Sefe) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (Sge) for a non-trivial class of graphs. |
Handle: | http://hdl.handle.net/11391/1326706 |
ISBN: | 9783662458020 9783662458037 |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |