Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Mad at Edge Crossings? Break the Edges!
verfasst von : Till Bruckdorfer, Michael Kaufmann
Erschienen in: Fun with Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
One of the main principles for the effective visualization of graphs is the avoidance of edge crossings. Around this problem, very active research has been performed with works ranging from combinatorics, to algorithmics, visualization effects, to psychological user studies. Recently, the pragmatic approach has been proposed to avoid crossings by drawing the edges only partially. Unfortunately, no formal model and efficient algorithms have been formulated to this end. We introduce the concept for drawings of graphs with partially drawn edges (
PED
). Therefore we consider graphs with and without given embedding and characterize
PEDs
with concepts like symmetry and homogeneity. For graphs without embedding we formulate a sufficient condition to guarantee a symmetric homogeneous
PED
, and identify a nontrivial graph class which has a symmetric homogeneous
PED
. For graphs with given layout we consider the variants of maximizing the shortest partially drawn edge and the total length respectively.