Publikation:

Simultaneous Orthogonal Planarity

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2016

Autor:innen

Angelini, Patrizio
Chaplick, Steven
Da Lozzo, Giordano
Di Battista, Giuseppe
Eades, Peter
Kindermann, Philipp
Kratochvíl, Jan
Lipp, Fabian
Rutter, Ignaz

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-319-50106-2_41
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

HU, Yifan, ed., Martin NÖLLENBURG, ed.. Graph Drawing and Network Visualization : 24th International Symposium, GD 2016 ; Revised Selected Papers. Cham: Springer, 2016, pp. 532-545. Lecture Notes in Computer Science. 9801. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_41

Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

GD 2016 : 24th International Symposium on Graph Drawing and Network Visualization, 19. Sept. 2016 - 21. Sept. 2016, Athens, Greece
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690ANGELINI, 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. Sept. 2016 - 21. Sept. 2016. In: HU, Yifan, ed., Martin NÖLLENBURG, ed.. Graph Drawing and Network Visualization : 24th International Symposium, GD 2016 ; Revised Selected Papers. Cham: Springer, 2016, pp. 532-545. Lecture Notes in Computer Science. 9801. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_41
BibTex
@inproceedings{Angelini2016-12-08Simul-39737,
  year={2016},
  doi={10.1007/978-3-319-50106-2_41},
  title={Simultaneous Orthogonal Planarity},
  number={9801},
  isbn={978-3-319-50105-5},
  issn={0302-9743},
  publisher={Springer},
  address={Cham},
  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:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39737">
    <dc:contributor>Rutter, Ignaz</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/39737"/>
    <dc:contributor>Kratochvíl, Jan</dc:contributor>
    <dcterms:issued>2016-12-08</dcterms:issued>
    <dc:contributor>Da Lozzo, Giordano</dc:contributor>
    <dc:contributor>Lipp, Fabian</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-08-02T11:50:15Z</dc:date>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:contributor>Chaplick, Steven</dc:contributor>
    <dc:creator>Eades, Peter</dc:creator>
    <dc:creator>Da Lozzo, Giordano</dc:creator>
    <dc:creator>Kratochvíl, Jan</dc:creator>
    <dc:creator>Rutter, Ignaz</dc:creator>
    <dc:creator>Di Battista, Giuseppe</dc:creator>
    <dc:language>eng</dc:language>
    <dc:contributor>Di Battista, Giuseppe</dc:contributor>
    <dc:contributor>Kindermann, Philipp</dc:contributor>
    <dc:creator>Angelini, Patrizio</dc:creator>
    <dc:creator>Kindermann, Philipp</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Eades, Peter</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Chaplick, Steven</dc:creator>
    <dc:creator>Lipp, Fabian</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>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-08-02T11:50:15Z</dcterms:available>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:contributor>Angelini, Patrizio</dc:contributor>
    <dcterms:title>Simultaneous Orthogonal Planarity</dcterms:title>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen