Arrow Research search

Author name cluster

Bojan Mohar

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.

15 papers
2 author rows

Possible papers

15

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.

Details

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.

Details

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.

Details DOI

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details