Source author record

Jiří Fiala

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Data Structures and Algorithms Computational Complexity Computational Geometry

Catalog footprint

Research overview

7works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the edge-length ratio of 2-trees

We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. 770 (2019), 88--94] and, for any given constant $r$ , we provide a $2$ -tree which does not admit a planar straight-line drawing with a ratio bounded by $r$ . When the ratio is restricted to adjacent edges only, we prove that any $2$ -tree admits a planar straight-line drawing whose edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small $\varepsilon > 0$ , hence the upper bound on the local edge-length ratio of partial $2$ -trees is $4$ .

preprint2015arXiv

Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems

We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique width. We rephrase the distance constrained graph labeling problem as a specific uniform variant of the Channel Assignment problem and show that this problem is fixed parameter tractable when parameterized by the neighborhood diversity together with the largest weight. Consequently, every $L(p_1, p_2, \dots, p_k)$ -labeling problem is FPT when parameterized by the neighborhood diversity, the maximum $p_i$ and $k.$ Our results yield also FPT algorithms for all $L(p_1, p_2, \dots, p_k)$ -labeling problems when parameterized by the size of a minimum vertex cover, answering an open question of Fiala et al.: Parameterized complexity of coloring problems: Treewidth versus vertex cover. The same consequence applies on Channel Assignment when the maximum weight is additionally included among the parameters. Finally, we show that the uniform variant of the Channel Assignment problem becomes NP-complete when generalized to graphs of bounded clique width.

preprint2014arXiv

Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs

A graph $G$ covers a graph $H$ if there exists a locally bijective homomorphism from $G$ to $H$ . We deal with regular covers in which this locally bijective homomorphism is prescribed by an action of a subgroup of ${\rm Aut}(G)$ . Regular covers have many applications in constructions and studies of big objects all over mathematics and computer science. We study computational aspects of regular covers that have not been addressed before. The decision problem RegularCover asks for two given graphs $G$ and $H$ whether $G$ regularly covers $H$ . When $|H|=1$ , this problem becomes Cayley graph recognition for which the complexity is still unresolved. Another special case arises for $|G| = |H|$ when it becomes the graph isomorphism problem. Therefore, we restrict ourselves to graph classes with polynomially solvable graph isomorphism. Inspired by Negami, we apply the structural results used by Babai in the 1970's to study automorphism groups of graphs. Our main result is the following FPT meta-algorithm: Let $\cal C$ be a class of graphs such that the structure of automorphism groups of 3-connected graphs in $\cal C$ is simple. Then we can solve RegularCover for $\cal C$ -inputs $G$ in time $O^*(2^{e(H)/2})$ where $e(H)$ denotes the number of the edges of $H$ . As one example of $\cal C$ , this meta-algorithm applies to planar graphs. In comparison, testing general graph covers is known to be NP-complete for planar inputs $G$ even for small fixed graphs $H$ such as $K_4$ or $K_5$ . Most of our results also apply to general graphs, in particular the complete structural understanding of regular covers for 2-cuts.

preprint2014arXiv

Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph G allows a homomorphism to a given graph H that is locally bijective, surjective, or injective, respectively, are NP-complete, even when G has pathwidth at most 5, 4, or 2, respectively, or when both G and H have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if G has bounded treewidth and in addition G or H has bounded maximum degree.

preprint2014arXiv

Universality of intervals of line graph order

We prove that for every $d\geq 3$ the homomorphism order of the class of line graphs of finite graphs with maximal degree $d$ is universal. This means that every finite or countably infinite partially ordered set may be represented by line graphs of graphs with maximal degree $d$ ordered by the existence of a homomorphism.

preprint2013arXiv

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

Hung and Chang showed that for all k>=1 an interval graph has a path cover of size at most k if and only if its scattering number is at most k. They also showed that an interval graph has a Hamilton cycle if and only if its scattering number is at most 0. We complete this characterization by proving that for all k<=-1 an interval graph is -(k+1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(m+n) time algorithm for computing the scattering number of an interval graph with n vertices an m edges, which improves the O(n^4) time bound of Kratsch, Kloks and Müller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(m+n) time.

preprint2010arXiv

The packing chromatic number of the square lattice is at least 12

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set $V(G)$ can be partitioned into disjoint classes $X_1, ..., X_k$ , where vertices in $X_i$ have pairwise distance greater than $i$ . For the 2-dimensional square lattice $\mathbb{Z}^2$ it is proved that $χ_ρ(\mathbb{Z}^2) \geq 12$ , which improves the previously known lower bound 10.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jiří Fiala

Research overview

Is this your work?

7 publications

On the edge-length ratio of 2-trees

Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems

Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs

Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree

Universality of intervals of line graph order

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs

The packing chromatic number of the square lattice is at least 12

See the researcher in context

Building this map preview