Angle and Distance Constraints on Tree Drawings

Brandes, Ulrik; Schlieper, Barbara

Angle and Distance Constraints on Tree Drawings

Dateien

bs_adctd_06.pdfGröße: 561.76 KBDownloads: 809

Datum

2007

Autor:innen

Brandes, Ulrik

Schlieper, Barbara

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

KAUFMANN, Michael, ed., Dorothea WAGNER, ed.. Graph Drawing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 54-65. Lecture Notes in Computer Science. ISBN 978-3-540-70903-9. Available under: doi: 10.1007/978-3-540-70904-6_7

Zusammenfassung

We consider planar drawings of trees that must satisfy constraints on the angles between edges incident to a common vertex and on the distances between adjacent vertices. These requirements arise naturally in many applications such as drawing phylogenetic trees or route maps. For straight-line drawings, either class of constraints is always realizable, whereas their combination is not in general. We show that straight-line realizability can be tested in linear time, and give an algorithm that produces drawing satisfying both groups of constraints together in a model where edges are represented as polylines with at most two bends per edge or as continuously differentiable curves.

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

BRANDES, Ulrik, Barbara SCHLIEPER, 2007. Angle and Distance Constraints on Tree Drawings. In: KAUFMANN, Michael, ed., Dorothea WAGNER, ed.. Graph Drawing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 54-65. Lecture Notes in Computer Science. ISBN 978-3-540-70903-9. Available under: doi: 10.1007/978-3-540-70904-6_7

BibTex

@inproceedings{Brandes2007Angle-5830,
  year={2007},
  doi={10.1007/978-3-540-70904-6_7},
  title={Angle and Distance Constraints on Tree Drawings},
  isbn={978-3-540-70903-9},
  publisher={Springer Berlin Heidelberg},
  address={Berlin, Heidelberg},
  series={Lecture Notes in Computer Science},
  booktitle={Graph Drawing},
  pages={54--65},
  editor={Kaufmann, Michael and Wagner, Dorothea},
  author={Brandes, Ulrik and Schlieper, Barbara}
}

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/5830">
    <dcterms:title>Angle and Distance Constraints on Tree Drawings</dcterms:title>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5830/1/bs_adctd_06.pdf"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:format>application/pdf</dc:format>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5830"/>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dcterms:issued>2007</dcterms:issued>
    <dc:creator>Schlieper, Barbara</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:25Z</dcterms:available>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dcterms:bibliographicCitation>First publ. in: Proceedings of the 14th International Symposium Graph Drawing (GD ´06) (LNCS 4372), 2007, pp. 54-65</dcterms:bibliographicCitation>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:25Z</dc:date>
    <dc:contributor>Schlieper, Barbara</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">We consider planar drawings of trees that must satisfy constraints on the angles between edges incident to a common vertex and on the distances between adjacent vertices. These requirements arise naturally in many applications such as drawing phylogenetic trees or route maps. For straight-line drawings, either class of constraints is always realizable, whereas their combination is not in general. We show that straight-line realizability can be tested in linear time, and give an algorithm that produces drawing satisfying both groups of constraints together in a model where edges are represented as polylines with at most two bends per edge or as continuously differentiable curves.</dcterms:abstract>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5830/1/bs_adctd_06.pdf"/>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja