Bojan Mohar

SODA Conference 2024 Conference Paper

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic

• Jesse Campion Loth
• Kevin Halasz
• Tomás Masarík
• Bojan Mohar
• Robert Sámal

A random 2-cell embedding of a connected graph G in some orientable surface is obtained by choosing a random local rotation around each vertex. Under this setup, the number of faces or the genus of the corresponding 2-cell embedding becomes a random variable. Random embeddings of two particular graph classes - those of a bouquet of n loops and those of n parallel edges connecting two vertices - have been extensively studied and are well-understood. However, little is known about more general graphs despite their important connections with central problems in mainstream mathematics and in theoretical physics (see [Lando & Zvonkin, Graphs on surfaces and their applications, Springer 2004]). There are also tight connections with problems in computing (random generation, approximation algorithms). The results of this paper, in particular, explain why Monte Carlo methods (see, e. g. , [Gross & Tucker, Local maxima in graded graphs of imbeddings, Ann. NY Acad. Sci 1979] and [Gross & Rieper, Local extrema in genus stratified graphs, JGT 1991]) cannot work for approximating the minimum genus of graphs. In his breakthrough work ([Stahl, Permutation-partition pairs, JCTB 1991] and a series of other papers), Stahl developed the foundation of “random topological graph theory”. Most of his results have been unsurpassed until today. In our work, we analyze the expected number of faces of random embeddings (equivalently, the average genus) of a graph G. It was very recently shown [Campion Loth & Mohar, Expected number of faces in a random embedding of any graph is at most linear, CPC 2023] that for any graph G, the expected number of faces is at most linear. We show that the actual expected number of faces F(G) is almost always much smaller. In particular, we prove the following results: (1) ½ ln n - 2 < 𝔼 [F (K n )] ≤ 3. 65 ln n+ o(1). This substantially improves Stahl's n + ln n upper bound for this case. (2) For random graphs G(n, p) (p = p(n)), we have. (3) For random models B(n, Δ) containing only graphs, whose maximum degree is at most Δ, we obtain stronger bounds by showing that the expected number of faces is Θ(ln n ). * The full version of our paper available on arXiv https: //arxiv. org/abs/2211. 01032.

FOCS Conference 2024 Conference Paper

Three-Edge-Coloring Projective Planar Cubic Graphs: A Generalization of the Four Color Theorem

• Yuta Inoue
• Ken-ichi Kawarabayashi
• Atsuyuki Miyashita
• Bojan Mohar
• Tomohiro Sonobe

We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In other words, the only (nontrivial) snark that can be embedded in the projective plane is the Petersen graph. This implies that a 2-connected cubic (multi)graph that can be embedded in the projective plane is not 3-edge-colorable if and only if it can be obtained from the Petersen graph by replacing each vertex by a 2-edge-connected planar cubic (multi)graph. Here, a replacement of a vertex $v$ in a cubic graph $G$ is the operation that takes a 2-connected planar (cubic) multigraph $H$ containing some vertex $u$ of degree 3, unifying $G-v$ and $H-u$, and connecting the vertices in $N_{G}[v]$ in $G-v$ with the three neighbors of $u$ in $H-u$ with 3 edges. Any graph obtained in such a way is said to be Petersen-like. This result is a nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability. Using this result, we obtain the following algorithmic consequence. Input: A cubic graph $G$. Output: Either a 3-edge-coloring of $G$, an obstruction showing that $G$ is not 3-edge-colorable, or the conclusion that $G$ cannot be embedded in the projective plane (certified by exposing a forbidden minor for the projective plane contained in $G$ ). Time complexity: $O(n^{2})$, where $n=\vert V(G)\vert$. An unexpected consequence of this result is a coloring-flow duality statement for the projective plane: A cubic graph embedded in the projective plane is 3-edge-colorable if and only if its dual multigraph is 5-vertex-colorable. Moreover, we show that a 2-edge connected graph embedded in the projective plane admits a nowhere-zero 4-flow unless it is Petersen-like (in which case it does not admit nowhere-zero 4-flows). This proves a strengthening of the Tutte 4-flow conjecture for graphs on the projective plane. Some of our proofs require extensive computer verification. The necessary source codes, together with the input and output files and the complete set of more than 5000 reducible configurations, are available on Github 1 1 https: //github. com/edge-coloring. Refer to the “README. md” file in each directory for instructions on how to run each program. which can be considered as an addendum to this paper. Moreover, we provide pseudocodes for all our computer verifications.

TCS Journal 2021 Journal Article

Cops and robbers on oriented toroidal grids

• Sebastián González Hermosillo de la Maza
• Seyyed Aliasghar Hosseini
• Fiachra Knox
• Bojan Mohar
• Bruce Reed

The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13.

SODA Conference 2018 Conference Paper

A submodular measure and approximate Gomory-Hu theorem for packing odd trails

• Ross Churchley
• Bojan Mohar

FOCS Conference 2018 Conference Paper

Efficient Polynomial-Time Approximation Scheme for the Genus of Dense Graphs

• Bojan Mohar
• Yifan Jing

The results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. The running time of the algorithm is quadratic. Moreover, we extend the algorithm to output an embedding (rotation system), whose genus is arbitrarily close to the minimum genus. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and the expected running time is also quadratic.

SODA Conference 2016 Conference Paper

Weak duality for packing edge-disjoint odd ( u, v )-trails

• Ross Churchley
• Bojan Mohar
• Hehui Wu

Despite Menger's famous duality between packings and coverings of ( u, v )-paths in a graph, there is no duality when we require the paths be odd: a graph with no two edge-disjoint odd ( u, v )-paths may need an arbitrarily large number of edges to cover all such paths. In this paper, we study the relaxed problem of packing odd trails. Our main result is an approximate duality for odd trails: if ν ( u, v ) denotes the maximum number of edge-disjoint ( u, v )-trails of odd length in a graph G and τ ( u, v ) denotes the minimum number of edges that intersect every such trail, then The proof leads to a polynomial-time algorithm to find, for any given k, either k edge-disjoint odd ( u, v )-trails or a set of fewer than 8 k edges intersecting all odd ( u, v )-trails. This yields a constant factor approximation algorithm for the packing number ν ( u, v ). This result generalizes to the setting of signed graphs and to the setting of group-labelled graphs, in which case “odd length” is replaced by “non-unit product of labels”. The motivation for this result comes from the study of totally odd graph immersions, and our results explain, in particular, why there is an essential difference between the totally odd weak and strong immersions.

SODA Conference 2015 Conference Paper

Four terminal planar Delta-Wye reducibility via rooted K 2, 4 minors

• Lino Demasi
• Bojan Mohar

A graph with four special vertices (called terminals) is wye-delta reducible if we can obtain a graph on four vertices by a sequence of wye-delta and delta-wye operations and series-parallel reductions, none of which is allowed to remove any of the terminals. A good characterization of wye-delta reducible 3-connected planar graphs with four terminals is given. The proofs yield an O ( n 2 ) time algorithm that either exhibits an obstruction to the 4-terminal reducibility or returns a sequence of wye-delta operations and series-parallel reductions that reduce the input graph to a subgraph of K 4 whose vertices are the terminals. We also discuss terminal wye-delta reducibility when a mixture of vertices and faces are treated as terminals. It is also shown that a sufficiently connected cubic graph is wye-delta reducible if and only if it does not contain the Petersen graph as a minor. The main ingredient in the proofs is a good characterization of planar graphs with four terminals that do not admit a rooted K 2, 4 minor with the four terminals corresponding to the roots on the large side of the bipartition of K 2, 4. Up to small connectivity reductions, cases without the rooted minor fall into five structural cases that lead to a polynomial-time algorithm for recognition of these graphs and construction of rooted K 2, 4 minors. This result is of independent interest in structural graph theory.

MFCS Conference 2010 Conference Paper

Do We Really Understand the Crossing Numbers?

• Bojan Mohar

Abstract The crossing number of a graph is the minimum number of crossings that occur in a drawing of the graph in the plane. This notion is natural and easy to understand, yet we do not know much about it apart from some basic properties. History, successes and pitfalls, some recent developments, and future directions will be presented.

SODA Conference 2009 Conference Paper

List-color-critical graphs on a fixed surface

• Ken-ichi Kawarabayashi
• Bojan Mohar

FOCS Conference 2008 Conference Paper

A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width

• Ken-ichi Kawarabayashi
• Bojan Mohar
• Bruce A. Reed

For every fixed surface S, orientable or non-orientable, and a given graph G, Mohar (STOC'96 and Siam J. Discrete Math. (1999)) described a linear time algorithm which yields either an embedding of G in S or a minor of G which is not embeddable in S and is minimal with this property. That algorithm, however, needs a lot of lemmas which spanned six additional papers. In this paper, we give a new linear time algorithm for the same problem. The advantages of our algorithm are the following: 1. The proof is considerably simpler: it needs only about 10 pages, and some results (with rather accessible proofs) from graph minors theory, while Mohar's original algorithm and its proof occupy more than 100 pages in total. 2. The hidden constant (depending on the genus g of the surface S) is much smaller. It is singly exponential in g, while it is doubly exponential in Mohar's algorithm. As a spinoff of our main result, we give another linear time algorithm, which is of independent interest. This algorithm computes the genus and constructs minimum genus embeddings of graphs of bounded tree-width. This resolves a conjecture by Neil Robertson and solves one of the most annoying long standing open question about complexity of algorithms on graphs of bounded tree-width.

SODA Conference 2008 Conference Paper

Finding one tight cycle

• Sergio Cabello
• Matt DeVos
• Jeff Erickson 0001
• Bojan Mohar

STOC Conference 2008 Conference Paper

Graph and map isomorphism and all polyhedral embeddings in linear time

• Ken-ichi Kawarabayashi
• Bojan Mohar

For every surface S (orientable or non-orientable), we give a linear time algorithm to test the graph isomorphism of two graphs, one of which admits an embedding of face-width at least 3 into S. This improves a previously known algorithm whose time complexity is n O(g) , where g is the genus of S. This is the first algorithm for which the degree of polynomial in the time complexity does not depend on g. The above result is based on two linear time algorithms, each of which solves a problem that is of independent interest. The first of these problems is the following one. Let S be a fixed surface. Given a graph G and an integer k ≥ 3, we want to find an embedding of G in S of face-width at least k, or conclude that such an embedding does not exist. It is known that this problem is NP-hard when the surface is not fixed. Moreover, if there is an embedding, the algorithm can give all embeddings of face-width at least k, up to Whitney equivalence. Here, the face-width of an embedded graph G is the minimum number of points of G in which some non-contractible closed curve in the surface intersects the graph. In the proof of the above algorithm, we give a simpler proof and a better bound for the theorem by Mohar and Robertson concerning the number of polyhedral embeddings of 3-connected graphs. The second ingredient is a linear time algorithm for map isomorphism and Whitney equivalence. This part generalizes the seminal result of Hopcroft and Wong that graph isomorphism can be decided in linear time for planar graphs.

SODA Conference 2007 Conference Paper

Approximation algorithms via contraction decomposition

• Erik D. Demaine
• MohammadTaghi Hajiaghayi
• Bojan Mohar

STOC Conference 2006 Conference Paper

Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs

• Ken-ichi Kawarabayashi
• Bojan Mohar

It is well-known (Feige and Kilian [24], Håstad [39]) that approximating the chromatic number within a factor of n 1-ε cannot be done in polynomial time for ε>0, unless coRP = NP. Computing the list-chromatic number is much harder than determining the chromatic number. It is known that the problem of deciding if the list-chromatic number is k, where k ≥ 3, is Π 2 p -complete [37].In this paper, we focus on minor-closed and odd-minor-closed families of graphs. In doing that, we may as well consider only graphs without K k -minors and graphs without odd K k -minors for a fixed value of k, respectively. Our main results are that there is a polynomial time approximation algorithm for the list-chromatic number of graphs without K k -minors and there is a polynomial time approximation algorithm for the chromatic number of graphs without odd-K k -minors. Their time complexity is O(n 3 ) and O(n 4 ), respectively. The algorithms have multiplicative error O(√log k) and additive error O(k), and the multiplicative error occurs only for graphs whose list-chromatic number and chromatic number are Θ(k), respectively.Let us recall that H has an odd complete minor of order l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Let us observe that the complete bipartite graph K n/2,n/2 contains a K k -minor for k ≤ n/2, but on the other hand, it does not contain an odd K k -minor for any k ≥ 3. Odd K 5 -minor-free graphs are closely related to one field of discrete optimization which is finding conditions under which a given polyhedron has integer vertices, so that integer optimization problems can be solved as linear programs. See [33, 34, 64]. Also, the odd version of the well-known Hadwiger's conjecture has been considered, see [28].Our main idea involves precoloring extension. This idea is used in many results; one example is Thomassen's proof on his celebrated theorem on planar graphs [69].The best previously known approximation for the first result is a simple O(k √log k)-approximation following algorithm that guarantees a list-coloring with O(k √log k) colors for K k -minor-free graphs. This follows from results of Kostochka [54, 53] and Thomason [67, 68].The best previous approximation for the second result comes from the recent result of Geelen et al. [28] who gave an O(k √log k)-approximation algorithm.We also relate our algorithm to the well-known conjecture of Hadwiger [38] and its odd version. In fact, we give an O(n 3 ) algorithm to decide whether or not a weaker version of Hadwiger's conjecture is true. Here, by a weaker version of Hadwiger's conjecture, we mean a conjecture which says that any 27k-chromatic graph contains a K k -minor. Also, we shall give an O(n 2500k ) algorithm for deciding whether or not any 2500k-chromatic graph contains an odd-K k -minor.Let us mention that this presentation consists of two papers which are merged into this one. The first one consists of results concerning minor-closed classes of graphs by two current authors, and the other consists of results concerning odd-minor-closed classes of graphs by the first author.

STOC Conference 1996 Conference Paper

Embedding Graphs in an Arbitrary Surface in Linear Time

• Bojan Mohar