Jan Kratochvíl

According to our database1, Jan Kratochvíl
  • authored at least 191 papers between 1986 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2017
MSOL restricted contractibility to planar graphs.
Theor. Comput. Sci., 2017

Algorithms and Characterizations for 2-Layer Fan-planarity: From Caterpillar to Stegosaurus.
J. Graph Algorithms Appl., 2017

On Vertex- and Empty-Ply Proximity Drawings.
CoRR, 2017

Extending Partial Representations of Interval Graphs.
Algorithmica, 2017

Extending Partial Representations of Proper and Unit Interval Graphs.
Algorithmica, 2017

2016
Computational complexity of covering three-vertex multigraphs.
Theor. Comput. Sci., 2016

On the hardness of switching to a small number of edges.
CoRR, 2016

Cops and Robbers on Intersection Graphs.
CoRR, 2016

Algorithmic Aspects of Regular Graph Covers.
CoRR, 2016

Simultaneous Orthogonal Planarity.
CoRR, 2016

Simultaneous Orthogonal Planarity.
Proceedings of the Graph Drawing and Network Visualization, 2016

On the Hardness of Switching to a Small Number of Edges.
Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems - (Extended Abstract).
Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

2015
Extending partial representations of subclasses of chordal graphs.
Theor. Comput. Sci., 2015

Testing Planarity of Partially Embedded Graphs.
ACM Trans. Algorithms, 2015

Distance constrained labeling on graphs with bounded neighborhood diversity.
CoRR, 2015

Completion of the Mixed Unit Interval Graphs Hierarchy.
Proceedings of the Theory and Applications of Models of Computation, 2015

Cops and Robbers on String Graphs.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

2-Layer Fan-Planarity: From Caterpillar to Stegosaurus.
Proceedings of the Graph Drawing and Network Visualization - 23rd International Symposium, 2015

2014
On Switching to H-Free Graphs.
Journal of Graph Theory, 2014

Firefighting on square, hexagonal, and triangular grids.
Discrete Mathematics, 2014

Locally injective k-colourings of planar graphs.
Discrete Applied Mathematics, 2014

Guest editors' foreword.
Discrete Applied Mathematics, 2014

Completion of the mixed unit interval graphs hierarchy.
CoRR, 2014

Planar Embeddings with Small and Uniform Faces.
CoRR, 2014

Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs.
CoRR, 2014

Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique.
CoRR, 2014

Contact Representations of Planar Graphs: Extending a Partial Representation is Hard.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Extending Partial Representations of Proper and Unit Interval Graphs.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

Computational Complexity of Covering Three-Vertex Multigraphs.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Planar Embeddings with Small and Uniform Faces.
Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Drawing Simultaneously Embedded Graphs with Few Bends.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

2013
Fast exact algorithm for L(2, 1)-labeling of graphs.
Theor. Comput. Sci., 2013

Preface.
Theor. Comput. Sci., 2013

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree.
Graphs and Combinatorics, 2013

Preface.
Eur. J. Comb., 2013

Preface.
Eur. J. Comb., 2013

Determining the L(2, 1)L(2, 1)-span in polynomial space.
Discrete Applied Mathematics, 2013

Linear-time Algorithm for Partial Representation Extension of Interval Graphs.
CoRR, 2013

A Kuratowski-type theorem for planarity of partially embedded graphs.
Comput. Geom., 2013

Non-crossing Connectors in the Plane.
Proceedings of the Theory and Applications of Models of Computation, 2013

Cops and Robbers on Intersection Graphs.
Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

2012
Segment representation of a subclass of co-planar graphs.
Discrete Mathematics, 2012

Guest editors' foreword.
Discrete Applied Mathematics, 2012

Parameterized complexity of generalized domination problems.
Discrete Applied Mathematics, 2012

Distance three labelings of trees.
Discrete Applied Mathematics, 2012

A note on planar partial 3-trees
CoRR, 2012

Extending Partial Representations of Proper and Unit Interval Graphs
CoRR, 2012

Extending Partial Representations of Subclasses of Chordal Graphs
CoRR, 2012

Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
CoRR, 2012

Extending partial representations of function graphs and permutation graphs
CoRR, 2012

Matching and l-Subgraph Contractibility to Planar Graphs
CoRR, 2012

A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs
CoRR, 2012

Non-crossing Connectors in the Plane
CoRR, 2012

Determining the L(2, 1)-Span in Polynomial Space.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

MSOL Restricted Contractibility to Planar Graphs.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

Extending Partial Representations of Subclasses of Chordal Graphs.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Beyond Homothetic Polygons: Recognition and Maximum Clique.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Extending Partial Representations of Function Graphs and Permutation Graphs.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Parameterized complexity of coloring problems: Treewidth versus vertex cover.
Theor. Comput. Sci., 2011

On the complexity of reconstructing H-free graphs from their Star Systems.
Journal of Graph Theory, 2011

Parameterized Problems Related to Seidel's Switching.
Discrete Mathematics & Theoretical Computer Science, 2011

Exact Algorithms for L(2, 1)-Labeling of Graphs.
Algorithmica, 2011

Branch and Recharge: Exact Algorithms for Generalized Domination.
Algorithmica, 2011

Extending Partial Representations of Interval Graphs.
Proceedings of the Theory and Applications of Models of Computation, 2011

Fast Exact Algorithm for L(2, 1)-Labeling of Graphs.
Proceedings of the Theory and Applications of Models of Computation, 2011

Can they cross? and how?: (the hitchhiker's guide to the universe of geometric intersection graphs).
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

A kuratowski-type theorem for planarity of partially embedded graphs.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010
Pursuing a fast robber on a graph.
Theor. Comput. Sci., 2010

Preface.
Discrete Mathematics, 2010

Guest Editors' Foreword.
Discrete Applied Mathematics, 2010

Testing Planarity of Partially Embedded Graphs.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Faithful Representations of Graphs by Islands in the Extended Grid.
Proceedings of the LATIN 2010: Theoretical Informatics, 2010

On the Computational Complexity of Degenerate Unit Distance Representations of Graphs.
Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

2009
Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs.
J. Graph Algorithms Appl., 2009

Sort and Search: Exact algorithms for generalized domination.
Inf. Process. Lett., 2009

On the computation of the hull number of a graph.
Discrete Mathematics, 2009

The capture time of a graph.
Discrete Mathematics, 2009

Untangling a Planar Graph.
Discrete & Computational Geometry, 2009

Guest editors' foreword.
Discrete Applied Mathematics, 2009

Parameterized Complexity of Generalized Domination Problems.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover.
Proceedings of the Theory and Applications of Models of Computation, 6th Annual Conference, 2009

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree.
Proceedings of the Graph Drawing, 17th International Symposium, 2009

2008
Intersection graphs of homothetic polygons.
Electronic Notes in Discrete Mathematics, 2008

On the computational complexity of partial covers of Theta graphs.
Discrete Applied Mathematics, 2008

Locally constrained graph homomorphisms - structure, complexity, and applications.
Computer Science Review, 2008

Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity.
Proceedings of the Theory and Applications of Models of Computation, 2008

Distance Constrained Labelings of Trees.
Proceedings of the Theory and Applications of Models of Computation, 2008

On the Complexity of Reconstructing H -free Graphs from Their Star Systems.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

On tractability of Cops and Robbers game.
Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

On Switching to H-Free Graphs.
Proceedings of the Graph Transformations, 4th International Conference, 2008

Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters.
Proceedings of the Graph Drawing, 16th International Symposium, GD 2008, Heraklion, Crete, 2008

2007
Dislocation dynamics - analytical description of the interaction force between dipolar loops.
Kybernetika, 2007

Preface.
Electronic Notes in Discrete Mathematics, 2007

On the Complexity of the Balanced Vertex Ordering Problem.
Discrete Mathematics & Theoretical Computer Science, 2007

Editorial.
Discrete Applied Mathematics, 2007

Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007

Branch and Recharge: Exact Algorithms for Generalized Domination.
Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Exact Algorithms for L (2, 1)-Labeling of Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Clustered Planarity: Small Clusters in Eulerian Graphs.
Proceedings of the Graph Drawing, 15th International Symposium, 2007

Moving Vertices to Make Drawings Plane.
Proceedings of the Graph Drawing, 15th International Symposium, 2007

Geometric Intersection Graphs: Do Short Cycles Help?
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

Homothetic Triangle Contact Representations of Planar Graphs.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2006
Coloring mixed hypertrees.
Discrete Applied Mathematics, 2006

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult.
Algorithmica, 2006

Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs.
Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

2005
Preface.
Theor. Comput. Sci., 2005

On the computational complexity of partial covers of Theta graphs.
Electronic Notes in Discrete Mathematics, 2005

Structural decompositions, width parameters, and graph labelings.
Discrete Applied Mathematics, 2005

Computing the branchwidth of interval graphs.
Discrete Applied Mathematics, 2005

Systems of distant representatives.
Discrete Applied Mathematics, 2005

On the Computational Complexity of the L(2, 1)-Labeling Problem for Regular Graphs.
Proceedings of the Theoretical Computer Science, 9th Italian Conference, 2005

Distance Constrained Labelings of Graphs of Bounded Treewidth.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

On the Complexity of the Balanced Vertex Ordering Problem.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004
Mixed hypercacti.
Discrete Mathematics, 2004

Elegant Distance Constrained Labelings of Trees.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

2003
Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs.
Theor. Comput. Sci., 2003

Complexity of Hypergraph Coloring and Seidel's Switching.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

Two Results on Intersection Graphs of Polygons.
Proceedings of the Graph Drawing, 11th International Symposium, 2003

2002
Guest Editors' Foreword.
J. Graph Algorithms Appl., 2002

On the complexity of bicoloring clique hypergraphs of graphs.
J. Algorithms, 2002

Partial covers of graphs.
Discussiones Mathematicae Graph Theory, 2002

On the injective chromatic number of graphs.
Discrete Mathematics, 2002

On the b-Chromatic Number of Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous.
Proceedings of the Algorithm Theory, 2002

Geometric Systems of Disjoint Representatives.
Proceedings of the Graph Drawing, 10th International Symposium, 2002

2001
Representing graphs by disks and balls (a survey of recognition-complexity results).
Discrete Mathematics, 2001

DIMATIA surveys (related to the Fifth Czech and Slovak Symposium on Combinatorics, Graph Theory, Algorithms and Applications held in Prague on July 6-11, 1998).
Discrete Mathematics, 2001

Foreword.
Discrete Mathematics, 2001

Efficient algorithms for graphs with few P4's.
Discrete Mathematics, 2001

Fixed-parameter complexity of lambda-labelings.
Discrete Applied Mathematics, 2001

Complexity of Coloring Graphs without Forbidden Induced Subgraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

Complexity Note on Mixed Hypergraphs.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Complexity of Partial Covers of Graphs.
Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

Distance Constrained Labeling of Precolored Trees.
Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

2000
Mod-2 Independence and Domination in Graphs.
Int. J. Found. Comput. Sci., 2000

Hom-properties are uniquely factorizable into irreducible factors.
Discrete Mathematics, 2000

Independent Sets with Domination Constraints.
Discrete Applied Mathematics, 2000

Coloring Mixed Hypertrees.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2000

On the complexity of bicoloring clique hypergraphs of graphs (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
Rankings of Directed Graphs.
SIAM J. Discrete Math., 1999

Mod-2 Independence and Domination in Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

Fixed-Parameter Complexity of lambda-Labelings.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

New Branchwidth Territories.
Proceedings of the STACS 99, 1999

1998
On the Complexity of Graph Covering Problems.
Nord. J. Comput., 1998

Brooks-type theorems for choosability with separation.
Journal of Graph Theory, 1998

Complexity of choosing subsets from color sets.
Discrete Mathematics, 1998

On intersection representations of co-planar graphs.
Discrete Mathematics, 1998

Disjoint and unfolding domination in graphs.
Australasian J. Combinatorics, 1998

Rankings of Directed Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

Independent Sets with Domination Constraints.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Crossing Number of Abstract Topological Graphs.
Proceedings of the Graph Drawing, 6th International Symposium, 1998

1997
Coloring precolored perfect graphs.
Journal of Graph Theory, 1997

Covering Regular Graphs.
J. Comb. Theory, Ser. B, 1997

On the computational complexity of (O, P)-partition problems.
Discussiones Mathematicae Graph Theory, 1997

Graphs maximal with respect to hom-properties.
Discussiones Mathematicae Graph Theory, 1997

Covering and coloring polygon-circle graphs.
Discrete Mathematics, 1997

Transversal Partitioning in Balanced Hypergraphs.
Discrete Applied Mathematics, 1997

Complexity of Colored Graph Covers I. Colored Directed Multigraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

Computational Complexity of the Krausz Dimension of Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

New trends in the theory of graph colorings: Choosability and list coloring.
Proceedings of the Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, 1997

1996
Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane.
Proceedings of the Graph Drawing, Symposium on Graph Drawing, 1996

1995
Generalized Domination in Chordal Graphs.
Nord. J. Comput., 1995

The Complexity of Induced Minors and Related Problems.
Algorithmica, 1995

Grid Intersection and Box Intersection Graphs on Surfaces (Extended Abstract).
Proceedings of the Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, 1995

1994
Intersection Graphs of Segments.
J. Comb. Theory, Ser. B, 1994

Intersection Dimensions of Graph Classes.
Graphs and Combinatorics, 1994

Regular codes in regular graphs are difficult.
Discrete Mathematics, 1994

Algorithmic complexity of list colorings.
Discrete Applied Mathematics, 1994

A Special Planar Satisfiability Problem and a Consequence of Its NP-completeness.
Discrete Applied Mathematics, 1994

Complexity of Graph Covering Problems.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

1993
One More Occurrence of Variables Makes Satisfiability Jump From Trivial to NP-Complete.
SIAM J. Comput., 1993

Satisfiability of Co-Nested Formulas.
Acta Inf., 1993

1992
Thresholds for classes of intersection graphs.
Discrete Mathematics, 1992

Compatible 2-factors.
Discrete Applied Mathematics, 1992

1991
Noncrossing Subgraphs in Topological Layouts.
SIAM J. Discrete Math., 1991

Proportional Graphs.
Random Struct. Algorithms, 1991

String graphs requiring exponential representations.
J. Comb. Theory, Ser. B, 1991

String graphs. II. recognizing string graphs is NP-hard.
J. Comb. Theory, Ser. B, 1991

String graphs. I. The number of critical nonstring graphs is infinite.
J. Comb. Theory, Ser. B, 1991

Induced minors and related problems.
Proceedings of the Graph Structure Theory, 1991

1988
On Restricted Two-Factors.
SIAM J. Discrete Math., 1988

On the number of Hamiltonian cycles in triangulations.
Journal of Graph Theory, 1988

On the Computational Complexity of Codes in Graphs.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

1986
Perfect codes over graphs.
J. Comb. Theory, Ser. B, 1986


  Loading...