Simultaneous Orthogonal Planarity

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

ANGELINI, Patrizio, Steven CHAPLICK, Sabine CORNELSEN, Giordano DA LOZZO, Giuseppe DI BATTISTA, Peter EADES, Philipp KINDERMANN, Jan KRATOCHVÍL, Fabian LIPP, Ignaz RUTTER, 2016. Simultaneous Orthogonal Planarity. GD 2016 : 24th International Symposium on Graph Drawing and Network Visualization. Athens, Greece, 19. Sep 2016 - 21. Sep 2016. In: HU, Yifan, ed., Martin NÖLLENBURG, ed.. Graph Drawing and Network Visualization : 24th International Symposium, GD 2016 ; Revised Selected Papers. GD 2016 : 24th International Symposium on Graph Drawing and Network Visualization. Athens, Greece, 19. Sep 2016 - 21. Sep 2016. Cham:Springer, pp. 532-545. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-50105-5

@inproceedings{Angelini2016-12-08Simul-39737, title={Simultaneous Orthogonal Planarity}, year={2016}, doi={10.1007/978-3-319-50106-2_41}, number={9801}, isbn={978-3-319-50105-5}, issn={0302-9743}, address={Cham}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Graph Drawing and Network Visualization : 24th International Symposium, GD 2016 ; Revised Selected Papers}, pages={532--545}, editor={Hu, Yifan and Nöllenburg, Martin}, author={Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano and Di Battista, Giuseppe and Eades, Peter and Kindermann, Philipp and Kratochvíl, Jan and Lipp, Fabian and Rutter, Ignaz} }

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/39737"> <dc:contributor>Kratochvíl, Jan</dc:contributor> <dc:contributor>Da Lozzo, Giordano</dc:contributor> <dc:contributor>Eades, Peter</dc:contributor> <dcterms:title>Simultaneous Orthogonal Planarity</dcterms:title> <dc:contributor>Lipp, Fabian</dc:contributor> <dc:creator>Kratochvíl, Jan</dc:creator> <dc:creator>Angelini, Patrizio</dc:creator> <dc:creator>Rutter, Ignaz</dc:creator> <dc:creator>Cornelsen, Sabine</dc:creator> <dc:creator>Chaplick, Steven</dc:creator> <dc:creator>Di Battista, Giuseppe</dc:creator> <dcterms:abstract xml:lang="eng">We introduce and study the ORTHOSEFE-k problem: Given k planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the k graphs? We show that the problem is NP-complete for k≥3 even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for k≥2 even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for k=2 when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge.</dcterms:abstract> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/39737"/> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dc:creator>Kindermann, Philipp</dc:creator> <dc:creator>Da Lozzo, Giordano</dc:creator> <dc:language>eng</dc:language> <dc:contributor>Chaplick, Steven</dc:contributor> <dc:creator>Lipp, Fabian</dc:creator> <dcterms:issued>2016-12-08</dcterms:issued> <dc:contributor>Kindermann, Philipp</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-08-02T11:50:15Z</dc:date> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-08-02T11:50:15Z</dcterms:available> <dc:contributor>Di Battista, Giuseppe</dc:contributor> <dc:contributor>Rutter, Ignaz</dc:contributor> <dc:creator>Eades, Peter</dc:creator> <dc:contributor>Angelini, Patrizio</dc:contributor> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto