Daniel Neuwirth

  1. On a Tree and a Path with no Geometric Simultaneous Embedding.

    Authors: Patrizio Angelini, Markus Geyer, Michael Kaufmann, Daniel Neuwirth
    Subjects: Computational Geometry
    Abstract

    Two graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ admit a geometric simultaneous
    embedding if there exists a set of points P and a bijection M: P -> V that
    induce planar straight-line embeddings both for $G_1$ and for $G_2$. While it
    is known that two caterpillars always admit a geometric simultaneous embedding
    and that two trees not always admit one, the question about a tree and a path
    is still open and is often regarded as the most prominent open problem in this
    area.

Syndicate content