Accueil

Antonios Symvonis

  1. Upward Point Set Embeddability for Convex Point Sets is in $P$.

    Wed, 08/17/2011 - 15:01 — SomNambul
    Authors: Tamara Mchedlidze, Antonios Symvonis, Michael Kaufmann
    Subjects: Data Structures and Algorithms
    Abstract

    In this paper, we present a polynomial dynamic programming algorithm that
    tests whether a $n$-vertex directed tree $T$ has an upward planar embedding
    into a convex point-set $S$ of size $n$. Further, we extend our approach to the
    class of outerplanar digraphs. This nontrivial and surprising result implies
    that any given digraph can be efficiently tested for an upward planar embedding
    into a given convex point set.

  2. Maximizing the Total Resolution of Graphs.

    Tue, 09/14/2010 - 15:02 — SomNambul
    Authors: Antonios Symvonis, Evmorfia N. Argyriou, Michael A. Bekos
    Subjects: Data Structures and Algorithms
    Abstract

    A major factor affecting the readability of a graph drawing is its
    resolution. In the graph drawing literature, the resolution of a drawing is
    either measured based on the angles formed by consecutive edges incident to a
    common node (angular resolution) or by the angles formed at edge crossings
    (crossing resolution). In this paper, we evaluate both by introducing the
    notion of "total resolution", that is, the minimum of the angular and crossing
    resolution. To the best of our knowledge, this is the first time where the
    problem of maximizing the total resolution of a drawing is studied.

  3. Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs.

    Wed, 09/16/2009 - 13:16 — SomNambul
    Authors: Tamara Mchedlidze, Antonios Symvonis
    Subjects: Data Structures and Algorithms
    Abstract

    In this paper we study the problem of existence of a crossing-free acyclic
    hamiltonian path completion (for short, HP-completion) set for embedded upward
    planar digraphs. In the context of book embeddings, this question becomes:
    given an embedded upward planar digraph $G$, determine whether there exists an
    upward 2-page book embedding of $G$ preserving the given planar embedding.

Math-arch

Syndicate content