Product structure of graphs with an excluded minor by Illingworth, F, Scott, A, Wood, D

“…Soc. 1990] and the Planar Graph Product Structure Theorem of Dujmović et al. …”

Interstreet crossing issues in single-row routing by Salleh, Shaharuddin

“…In this scenario, the nets can be modeled as nodes in a planar graph. However, inter-street crossings in the node axis are allowed, and they are necessary to prevent the nets from crossing each other. …”

An Extension of Kotzig’s Theorem by Aksenov Valerii A., Borodin Oleg V., Ivanova Anna O.

“…In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. …”
Get full text

Extremal density for sparse minors and subdivisions by Haslegrave, J, Kim, J, Liu, H

“…Among others, <br> (1+o(1))t2 average degree is sufficient to force the t×t grid as a topological minor; <br> (3/2+o(1))t average degree forces every t-vertex planar graph as a minor, and the constant 3/2 is optimal, furthermore, surprisingly, the value is the same for t-vertex graphs embeddable on any fixed surface; <br> a universal bound of (2+o(1))t on average degree forcing every t-vertex graph in any nontrivial minor-closed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth.…”

Accelerating dynamic programming by Weimann, Oren

Get full text

Study on the Design of Lepelletier Planetary Gear Mechanism Automatic Transmission by Jianxin Peng, Huanzhang Xue

“…The transmission which arranged with shifting elements is checked by the planar-graph. This method is used to optimize the 6~10 speed Lepelletier PGM. …”
Get full text

Completely independent spanning trees in some Cartesian product graphs by Xia Hong, Wei Feng

“…Hasunuma showed that there are two completely independent spanning trees in any 4-connected maximal planar graph, and that given a graph $ G $, the problem of deciding whether there exist two completely independent spanning trees in $ G $ is NP-complete. …”
Get full text

Algorithmic approaches to circuit enumeration problems and applications by Lee, Boon Chai

Get full text

Interstreet crossing issues in single-row routing by Salleh, Shaharuddin

“…In this scenario, the nets can be modeled as nodes in a planar graph. However, inter-street crossings in the node axis are allowed, and they are necessary to prevent the nets from crossing each other. …”
Get full text

Geographic routing with cross links by Zha, Wei, Ng, Wee Keong

“…Delivery on an incomplete planarized graph is not guaranteed. In this paper, we explore how exactly incomplete planarization leads to delivery failure and introduce an algorithm to solve this problem. …”
Get full text
Get full text

Double-simulated annealing model for mapping of graphs to single-row networks by Loh, Ser Lee, Salleh, Shaharudin, Sarmin, Nor Haniza

“…Thus, the effort to optim ize the ordering of vertices in connected graph for transf orm ation into a planar graph in the form of single-row network is carried out through the new interval form ation and Double Simulated Annealing (DSA).…”
Get full text

Linear choosability of graphs by Louis Esperet, Mickael Montassier, André Raspaud

“…In this paper, we investigate the linear choosability of graphs for some families of graphs: graphs with small maximum degree, with given maximum average degree, planar graphs... Moreover, we prove that determining whether a bipartite subcubic planar graph is lineary 3-colorable is an NP-complete problem.…”
Get full text

Universal quantum computation by scattering in the Fermi–Hubbard model by Ning Bao, Patrick Hayden, Grant Salton, Nathaniel Thomas

“…Therefore, simulating the model on planar graphs is as hard as simulating quantum computation. …”
Get full text

Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications by Demaine, Erik D., Hajiaghayi, Mohammad Taghi

“…Eppstein characterized minor-closed families of graphs with bounded local treewidth as precisely minor-closed families that minor-exclude an apex graph, where an apex graph has one vertex whose removal leaves a planar graph. In particular, Eppstein showed that all apex-minor-free graphs have bounded local treewidth, but his bound is doubly exponential in r, leaving open whether a tighter bound could be obtained. …”
Get full text

Internally 4-Connected Graphs With No {Cube, V8}-Minor by Lewchalermvongs Chanun, Ananchuen Nawarat

“…A cube is an internally 4-connected planar graph with eight vertices and twelve edges corresponding to the skeleton of the cube in the platonic solid, and the Wagner graph V8 is an internally 4-connected nonplanar graph obtained from a cube by introducing a twist. …”
Get full text

A solution to the Papadimitriou-Ratajczak conjecture by Moitra, Ankur

Get full text

Local limit theorem in random graphs and graphs on non-constant surfaces by Saller, S

“…We first find bounds on the sizes of these classes and prove that as long as g(n) = o(n/log^3(n)), the classes G^(g(n)) and H^(g(n)) both have a growth constant equal to the planar graph growth constant. As long as g(n) = O(n/log(n)) it is further shown that the classes G^g(n) and H^(g(n)) are both small. …”

Roman {2}-Bondage Number of a Graph by Moradi Ahmad, Mojdeh Doost Ali, Sharifi Omid

“…Specifically, it is known that the Roman bondage number of every planar graph does not exceed 15 (see [S. Akbari, M. Khatirinejad and S. …”
Get full text

A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph by Jonathan Li, Rohan Potru, Farhad Shahrokhi

“…Another advantage of the hybrid algorithm is to solve very large problems that are suitable for application of LP rounding (sparse graphs) but LP formulations become formidable in practice and LP solvers crash, as we observed on a real-world graph with 7.7 million+ vertices and a planar graph on 1,000,000 vertices.…”
Get full text

Robust distribution sensor network localization with noisy range measurements by Moore, David Christopher, 1981-

Get full text