Graph Theory Algorithms of Hamiltonian Cycle from Quasi-Spanning Tree and Domination Based on Vizing Conjecture by T. Anuradha, T. Lakshmi Surekha, Praveena Nuthakki, Bullarao Domathoti, Ganesh Ghorai, Faria Ahmed Shami

“…Similarly, in the three connected cubic planar graphs with two-colored faces, the vertex is incident to one blue and two red faces. …”
Get full text

PTAS for sparse general-valued CSPs by Mezei, B, Wrochna, M, Živný, S

“…Baker’s approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and Zivn´y [SODA’21] ˇ showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionallytreewidth-fragile classes, which is the most general “sparsity” condition for which a PTAS is known. …”

PTAS for sparse general-valued CSPs by Mezei, BF, Wrochna, M, Živný, S

“…We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes.Baker’s approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and Živný [SODA’21] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general "sparsity" condition for which a PTAS is known. …”

Edge-unfolding almost-flat convex polyhedral terrains by Chen, Yanping, M. Eng. Massachusetts Institute of Technology

Get full text

The Excluded Minors for Isometric Realizability in the Plane by Fiorini, Samuel, Huynh, Tony, Joret, Gwenaël, Varvitsiotis, Antonios

“…In addition, we give a family of examples that show that $f_\infty$ is unbounded on the class of planar graphs and $f_\infty$ is not bounded as a function of tree-width.…”
Get full text
Get full text

Unraveling the Reconfiguration Dynamics of Silver Nanowire Networks under Electrothermal Stress by Trebach, Adam Morris Willner

“…In the process of building our computational models of real nanowire networks, we develop several new image processing techniques that show great promise when applied to the challenging task of automatically extracting non-planar graphs from images.…”
Get full text

Using Language Models to Understand Molecular Structures by Fan, Vincent K.

“…OpenChemIE is most suited for information extraction on organic chemistry literature, where molecules are generally depicted as planar graphs or written in text and can be consolidated into a SMILES format. …”
Get full text

Approximation Algorithms via Contraction Decomposition by Hajiaghayi, Mohammad Taghi, Demaine, Erik D., Mohar, Bojan

Get full text
Get full text

Pairwise visual comparison of small RNA secondary structures with base pair probabilities by Serge Léger, Maria Beatriz Walter Costa, Dan Tulpan

“…Abstract Background Predicted RNA secondary structures are typically visualized using dot-plots for base pair binding probabilities and planar graphs for unique structures, such as the minimum free energy structure. …”
Get full text

On approximating projection games by Manurangsi, Pasin

Get full text

Closed quasigeodesics, escaping from polygons, and conflict-free graph coloring by Hesterberg, Adam Classen

Get full text

Reconfiguration of list edge-colorings in a graph by Ito, Takehiro, Kaminski, Marcin, Demaine, Erik D.

Get full text
Get full text

A Local Algorithm for Constructing Spanners in Minor-Free Graphs by Levi, Reut, Ron, Dana, Rubinfeld, Ronitt

“…One such family is the family of graphs with an excluded minor (which in particular includes planar graphs). For this family there is an algorithm that achieves constant success probability, and inspects (d/c)^{poly(h)log(1/c)} edges (for each edge it is queried on), where d is the maximum degree in the graph and h is the size of the excluded minor. …”
Get full text
Get full text

Contraction decomposition in h-minor-free graphs and algorithmic applications by Demaine, Erik D., Hajiaghayi, Mohammad Taghi, Kawarabayashi, Ken-ichi

“…For example, our approximation framework gives the first PTAS for TSP in weighted H-minor-free graphs, solving a decade-old open problem of Grohe; and gives another fixed-parameter algorithm for k-cut in H-minor-free graphs, which was an open problem of Downey et al. even for planar graphs. To obtain our contraction decompositions, we develop new graph structure theory to realize virtual edges in the clique-sum decomposition by actual paths in the graph, enabling the use of the powerful Robertson--Seymour Graph Minor decomposition theorem in the context of edge contractions (without edge deletions). …”
Get full text
Get full text

Graph coloring applied to secure computation in non-Abelian groups by Yao, Andrew Chi-Chih, Wang, Huaxiong, Desmedt, Yvo, Pieprzyk, Josef, Steinfeld, Ron, Sun, Xiaoming, Tartary, Christophe

“…We reduce the problem of constructing such protocols to a combinatorial coloring problem in planar graphs. We then give three constructions for such colorings. …”
Get full text
Get full text

Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem by Zhidong Zhang

“…The common feature for a nontrivial hard problem is the existence of nontrivial topological structures, non-planarity graphs, nonlocalities, or long-range spin entanglements in a model system with randomness. …”
Get full text

Simultaneous nearest neighbor search by Kleinberg, Robert, Yuan, Yang, Indyk, Piotr, Mahabadi, Sepideh

“…Furthermore, we show that the approximation factor can be in fact reduced to a constant for compatibility graphs frequently occurring in practice, e.g., 2D grids, 3D grids or planar graphs. Finally, we validate our theoretical results by preliminary experiments. …”
Get full text
Get full text
Get full text

Random Graphs Containing Few Disjoint Excluded Minors by McDiarmid, C, Kurauskas, V

“…Robertson and Seymour (1986) give an extension concerning any minor-closed class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} of graphs, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, there is a set B of at most g(k) vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. …”

Combinatorics related to the totally nonnegative Grassmannian by Oh, SuHo

Get full text

Modularity of networks by Skerman, F

“…This shows random planar graphs typically have modularity 1 + <em>o</em>(1).…”