Jiří Fiala

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 of the path. It is known that, if S is sufficiently large, there exist three edge-disjoint plane Hamiltonian paths on S. In this paper we study an edge-constrained version of the problem of finding Hamiltonian paths on a point set. We first consider the problem of finding a single plane Hamiltonian path pi with endpoints s, t in S and constraints given by a segment ab, where a, b in S. We consider the following scenarios: (i) ab in pi; (ii) ab not in pi. We characterize those quintuples (S, a, b, s, t) for which pi exists. Secondly, we consider the problem of finding two plane Hamiltonian paths pi_1, pi_2 on a set S with constraints given by a segment ab, where a, b in S. We consider the following scenarios: (i) pi_1 and pi_2 share no edges and ab is an edge of pi_1; (ii) pi_1 and pi_2 share no edges and none of them includes ab as an edge; (iii) both pi_1 and pi_2 include ab as an edge and share no other edges. In all cases, we characterize those triples (S, a, b) for which pi_1 and pi_2 exist.

The notion of graph covers is a discretization of covering spaces introduced and deeply studied in topology. In discrete mathematics and theoretical computer science, they have attained a lot of attention from both the structural and complexity perspectives. Nonetheless, disconnected graphs were usually omitted from the considerations with the explanation that it is sufficient to understand coverings of the connected components of the target graph by components of the source one. However, different (but equivalent) versions of the definition of covers of connected graphs generalize to non-equivalent definitions for disconnected graphs. The aim of this paper is to summarize this issue and to compare three different approaches to covers of disconnected graphs: 1) locally bijective homomorphisms, 2) globally surjective locally bijective homomorphisms (which we call \emph{surjective covers}), and 3) locally bijective homomorphisms which cover every vertex the same number of times (which we call \emph{equitable covers}). The standpoint of our comparison is the complexity of deciding if an input graph covers a fixed target graph. We show that both surjective and equitable covers satisfy what certainly is a natural and welcome property: covering a disconnected graph is polynomial-time decidable if such it is for every connected component of the graph, and it is NP-complete if it is NP-complete for at least one of its components. We further argue that the third variant, equitable covers, is the most natural one, namely when considering covers of colored graphs. Moreover, the complexity of surjective and equitable covers differ from the fixed parameter complexity point of view. In line with the current trends in topological graph theory, as well as its applications in mathematical physics, we consider graphs in a very general sense[...]