Drawing trees in a streaming model

Binucci, Carla; Brandes, Ulrik; Di Battista, Giuseppe; Didimo, Walter; Gaertler, Marco; Palladino, Pietro; Patrignani, Maurizio; Symvonis, Antonios; Zweig, Katharina

Drawing trees in a streaming model

Dateien

Binucci_209262.pdfGröße: 132.32 KBDownloads: 255

Datum

2012

Autor:innen

Binucci, Carla

Brandes, Ulrik

Di Battista, Giuseppe

Didimo, Walter

Gaertler, Marco

Palladino, Pietro

Patrignani, Maurizio

Symvonis, Antonios

Zweig, Katharina

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

Information Processing Letters. 2012, 112(11), pp. 418-422. ISSN 0020-0190. eISSN 0020-0190. Available under: doi: 10.1016/j.ipl.2012.02.011

Zusammenfassung in einer weiteren Sprache

We pose a new visualization challenge, asking Graph Drawing algorithms to cope with the requirements of Streaming applications. In this model a source produces a graph one edge at a time. When an edge is produced, it is immediately drawn and its placement cannot be altered. The drawing has an image persistence, that controls the lifetime of edges. If the persistence is k, an edge remains in the drawing for the time spent by the source to generate k edges, and then it fades away. In this model we study the area requirement of planar straight-line grid drawings of trees and we assess the output quality of the presented algorithms by computing the competitive ratio with respect to the best known offline algorithms.

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

BINUCCI, Carla, Ulrik BRANDES, Giuseppe DI BATTISTA, Walter DIDIMO, Marco GAERTLER, Pietro PALLADINO, Maurizio PATRIGNANI, Antonios SYMVONIS, Katharina ZWEIG, 2012. Drawing trees in a streaming model. In: Information Processing Letters. 2012, 112(11), pp. 418-422. ISSN 0020-0190. eISSN 0020-0190. Available under: doi: 10.1016/j.ipl.2012.02.011

BibTex

@article{Binucci2012Drawi-20926,
  year={2012},
  doi={10.1016/j.ipl.2012.02.011},
  title={Drawing trees in a streaming model},
  number={11},
  volume={112},
  issn={0020-0190},
  journal={Information Processing Letters},
  pages={418--422},
  author={Binucci, Carla and Brandes, Ulrik and Di Battista, Giuseppe and Didimo, Walter and Gaertler, Marco and Palladino, Pietro and Patrignani, Maurizio and Symvonis, Antonios and Zweig, Katharina}
}

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/20926">
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/20926/2/Binucci_209262.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/20926"/>
    <dc:language>eng</dc:language>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-11-23T08:54:15Z</dc:date>
    <dcterms:title>Drawing trees in a streaming model</dcterms:title>
    <dc:contributor>Symvonis, Antonios</dc:contributor>
    <dc:rights>terms-of-use</dc:rights>
    <dc:creator>Zweig, Katharina</dc:creator>
    <dc:creator>Binucci, Carla</dc:creator>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dc:contributor>Zweig, Katharina</dc:contributor>
    <dc:creator>Gaertler, Marco</dc:creator>
    <dc:contributor>Binucci, Carla</dc:contributor>
    <dc:contributor>Gaertler, Marco</dc:contributor>
    <dc:contributor>Di Battista, Giuseppe</dc:contributor>
    <dc:contributor>Palladino, Pietro</dc:contributor>
    <dc:creator>Palladino, Pietro</dc:creator>
    <dc:creator>Patrignani, Maurizio</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Didimo, Walter</dc:creator>
    <dc:contributor>Patrignani, Maurizio</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Di Battista, Giuseppe</dc:creator>
    <dcterms:bibliographicCitation>Information Processing Letters ; 112 (2012), 11. - S. 418-422</dcterms:bibliographicCitation>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-11-23T08:54:15Z</dcterms:available>
    <dc:contributor>Didimo, Walter</dc:contributor>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/20926/2/Binucci_209262.pdf"/>
    <dcterms:issued>2012</dcterms:issued>
    <dc:creator>Symvonis, Antonios</dc:creator>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja