Arrow Research search

Author name cluster

Vida Dujmovic

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
1 author row

Possible papers

12

FOCS Conference 2023 Conference Paper

Proof of the Clustered Hadwiger Conjecture

  • Vida Dujmovic
  • Louis Esperet
  • Pat Morin
  • David R. Wood

Hadwiger’s Conjecture asserts that every $K_{h}$-minor-free graph is properly $(h-1)$-colourable. We prove the following improper analogue of Hadwiger’s Conjecture: for fixed h, every $K_{h}$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. It solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed $t \geqslant s$, we show that every $K_{s, t}$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van den Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. For an excluded apex minor, we strengthen the result as follows: for fixed $t \geqslant s \geqslant 3$, and for any fixed apex graph X, every $K_{s, t}$-subgraph-free X-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is again best possible.

Details

FOCS Conference 2020 Conference Paper

Adjacency Labelling for Planar Graphs (and Beyond)

  • Vida Dujmovic
  • Louis Esperet
  • Cyril Gavoille
  • Gwenaël Joret
  • Piotr Micek
  • Pat Morin

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an $n$ -vertex planar graph $G$ is assigned a $(1+o(1))\text{log}_{2}n$ -bit label and the labels of two vertices $u$ and $v$ are sufficient to determine if $uv$ is an edge of $G$. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer $n$, there exists a graph $U_{n}$ with $n^{1+o(1)}$ vertices such that every $n$ -vertex planar graph is an induced subgraph of $U_{n}$. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and $k$ -planar graphs.

Details

FOCS Conference 2019 Conference Paper

Planar Graphs have Bounded Queue-Number

  • Vida Dujmovic
  • Gwenaël Joret
  • Piotr Micek
  • Pat Morin
  • Torsten Ueckerdt
  • David R. Wood

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes.

Details

FOCS Conference 2013 Conference Paper

Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring

  • Vida Dujmovic
  • Pat Morin
  • David R. Wood

Graph separators are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that the separator can be as large as Ω(√n) in graphs with n vertices. This is the case for planar graphs, and more generally, for proper minor-closed families. We study a special type of graph separator, called a layered separator, which may have linear size in n, but has bounded size with respect to a different measure, called the breadth. We prove that a wide class of graphs admit layered separators of bounded breadth, including graphs of bounded Euler genus. We use layered separators to prove Õ(log n) bounds for a number of problems where O(√n) was a long standing previous best bound. This includes the nonrepetitive chromatic number and queue-number of graphs with bounded Euler genus. We extend these results to all proper minor-closed families, with a O(log n) bound on the nonrepetitive chromatic number, and a log O(1) n bound on the queue-number. Only for planar graphs were log O(1) n bounds previously known. Our results imply that every graph from a proper minor-closed class has a 3-dimensional grid drawing with n log O(1) n volume, whereas the previous best bound was O(n 3/2 ). Readers interested in the full details should consult arXiv: 1302. 0304 and arXiv: 1306. 1595, rather than the current extended abstract.

Details

ICRA Conference 1999 Conference Paper

Efficient Topological Exploration

  • Ioannis M. Rekleitis
  • Vida Dujmovic
  • Gregory Dudek

We consider the robot exploration of a planar graph-like world. The robot's goal is to build a complete map of its environment. The environment is modeled as an arbitrary undirected planar graph which is initially unknown to the robot. The robot cannot distinguish vertices and edges that it has explored from the unexplored ones. The robot is assumed to be able to autonomously traverse graph edges, recognize when it has reached a vertex, and enumerate edges incident upon the current vertex. The robot cannot measure distances nor does it have a compass, but it is equipped with a single marker that it can leave at a vertex and sense if the marker is present at a newly visited vertex. The total number of edges traversed while constructing a map of a graph is used as a measure of performance. We present an efficient algorithm for learning an unknown, undirected planar graph by a robot equipped with one marker. Experimental results obtained by running a large collection of example worlds are presented.

Details
v2026.09.13