6 papers
How Close is a Tree to a Euclidean Minimum Spanning Tree?
Todor AntiÄ, JiÅà Fiala, Jelena GliÅ¡iÄ +8
Let be a straight-line crossing-free drawing of a tree . A \emph{bad pair} in is a pair of non-adjacent vertices of whose Euclidean distance in is smaller tha…
Edge-Constrained Hamiltonian Paths on a Point Set
Todor AntiÄ, Aleksa Džuklevski, JiÅà Fiala +5
Let S be a set of distinct points in general position in the Euclidean plane. A plane Hamiltonian path on S is a crossing-free geometric path such that every point of S is a vertex…
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
Jan Bok, JiÅà Fiala, Petr HlinÄný +2
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for {\em graphs with semi-edges}. The notion of graph covering is a…
Outerplanar and Forest Storyplans
JiÅÃ Fiala, Jiří Fiala, Oksana Firman +3
We study the problem of gradually representing a complex graph as a sequence of drawings of small subgraphs whose union is the complex graph. The sequence of drawings is called \em…
Computational complexity of covering regular trees
Jan Bok, JiÅà Fiala, Nikola JedliÄková +1
A graph covering projection, also referred to as a locally bijective homomorphism, is a mapping between the vertices and edges of two graphs that preserves incidences and is a loca…
Computational Complexity of Covering Colored Mixed Multigraphs with Simple Degree Partitions
Jan Bok, JiÅà Fiala, Nikola JedliÄková +2
The notion of graph covers (also referred to as locally bijective homomorphisms) plays an important role in topological graph theory and has found its computer science applications…