arxiv: 2605.08016 · v1 · submitted 2026-05-08 · 💻 cs.DS · cs.CC· cs.DM

Recognition: no theorem link

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist

Archit Chauhan, Kilian Rothmund, Rohit Gurjar, Thomas Thierauf

Authors on Pith no claims yet

Pith reviewed 2026-05-11 02:28 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.DM

keywords planarizing gadgets(k,l)-tight graphsgraph recognitionplanar graphsrigidity

0 comments

The pith

No planarizing gadgets exist for recognizing (k, l)-tight graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that planarizing gadgets do not exist for the problem of recognizing whether a graph is (k, l)-tight. This matters because the recognition problem already has efficient deterministic NC algorithms when restricted to planar graphs, yet no such algorithms are known for arbitrary graphs. A planarizing gadget would replace non-planar portions with local structures that keep the graph planar while preserving exactly whether the original graph satisfies the (k, l)-tightness condition. Since no such gadget can exist, the standard reduction technique that would transfer the planar algorithms to the general case is ruled out unconditionally.

Core claim

Planarizing gadgets for the problem of recognizing (k, l)-tight graphs do not exist. A planarizing gadget is a replacement structure inserted into a graph to eliminate crossings and produce a planar graph while preserving membership in the class of (k, l)-tight graphs.

What carries the argument

The formal definition of a planarizing gadget together with the unconditional proof that no finite local replacement can simultaneously enforce planarity and preserve (k, l)-tightness for every input graph.

If this is right

The recognition problem for general (k, l)-tight graphs cannot be solved by reducing it to the planar case via gadgets.
Efficient planar algorithms cannot be lifted to arbitrary graphs using the usual gadget technique.
Other algorithmic approaches besides planarization reductions are necessary for the general problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The structural gap between planar and non-planar (k, l)-tight graphs may be deeper than local modifications can bridge.
Similar non-existence results could hold for other combinatorial properties that admit efficient planar algorithms but lack them in general.
Researchers may need to develop parameterized or approximation algorithms rather than exact reductions to the planar setting.

Load-bearing premise

Any reduction from general graphs to planar graphs that preserves (k, l)-tightness must be realizable by a local planarizing gadget of the kind formally defined.

What would settle it

An explicit construction of a finite gadget that replaces any crossing or non-planar configuration, produces a planar graph, and leaves the (k, l)-tight property unchanged for all possible surrounding graphs would falsify the claim.

Figures

Figures reproduced from arXiv: 2605.08016 by Archit Chauhan, Kilian Rothmund, Rohit Gurjar, Thomas Thierauf.

**Figure 1.** Figure 1: The crossing ab, cd is resolved by adding a planarizing gadget could cross with multiple edges. We replace each crossing by a copy of Γ . When there are multiple crossings, one might need a more restricted gadget like the one in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

**Figure 2.** Figure 2: The crossing ab, cd is resolved by adding a more restricted gadget that also works for multiple crossings. 2.2 Connected components in sparse graphs For the proof of our main result we need the fact that for some sparse graphs, induced subgraphs with suciently many edges are always connected. Lemma 2.1. Let G = (V, E) be a (k, l)-sparse graph, where 1 k l 2k − 1. Then any subset S V with |E[S]| … view at source ↗

**Figure 3.** Figure 3: The graphs used in the proofs of Lemma 3.3 and Lemma 3.4 . Proof. Consider the (2, 0)-tight graph G = (V, E) in [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: The graphs for Lemma 3.4 for l = 3. Graph G is not (2, 3)-tight, but H1, H2 are. Analogously, we obtain a graph H2 by moving the edge (b, f) to (c, f) which is also (2, 3)- tight. We can construct similar graphs for the cases l = 0, 1, 2, see [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗

**Figure 5.** Figure 5: The graphs G for Lemma 3.4 for l = 0, 1, 2. The corresponding graphs H1 and H2 are defined analogously as in the case l = 3 in [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

**Figure 6.** Figure 6: Drawing of the gadget graph Γ with the sets S1, S2 from Lemma 3.4. Case 2. |S1 \ S2| = 1. Then we have |EΓ [S1 [ S2]| |EΓ [S1]| + |EΓ [S2]| 2|S1| − 3 + 2|S2| − 3 (4) = 2(|S1 [ S2| + 1) − 6 = 2|S1 [ S2| − 4 Inequality (4) follows from Lemma 3.4 and contradicts Lemma 3.2. Case 3. |S1 \ S2| 2. Then we have |EΓ [S1 [ S2]| |EΓ [S1]| + |EΓ [S2]| − |EΓ [S1 \ S2]| (5) 2|S1| − 3 + 2|S2| − 3 − (2|S1 \ S2| … view at source ↗

**Figure 6.** Figure 6: Observe that in this embedding, the set S2 naturally partitions the set S1 into three parts Sa, S1 \ S2, Sb such that a 2 Sa, b 2 Sb. Note that there cannot be any edges in the gadget with one end point in Sa and other end point in Sb. Vice versa, S1 partitions S2 into Sc, S1 \ S2, Sd. We give an upper bound on the number of edges in EΓ [S1] that contradicts Lemma 3.4. For x 2 {a, b, c, d} we de ne S 0 x =… view at source ↗

**Figure 7.** Figure 7: The same non-(2, 3)-tight graph in two different drawings: (a) Adding a gadget by deleting the edges ab, cd and connecting a new vertex x to a, b, c, d makes the graph (2, 3)- tight. (b) the same gadget preserves the non-(2, 3)-tightness. Acknowledgments We thank Meera Sitharam for pointing out the reduction from (k, l)-sparsity to max ow. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗

**Figure 8.** Figure 8: The flow problem (H, S, T, ce) as described in the reduction with ei = e. We argue that G is (k, l)-sparse i the ow problems (H, S, T, ce) have max ow m + l, for all e 2 E. By the max- ow min-cut theorem, we can argue via (S, T)-cuts in H. A set C VH is a (S, T)-cut, if S C and C \ T = ;. The capacity of cut C for capacity function ce is ce(C) = X u2C, v2VH\C ce(u, v). We will show that G not (k, l)-sp… view at source ↗

read the original abstract

The problem of recognizing (k, l)-tight graphs is a fundamental problem that has close connections to well studied problems like graph rigidity. The problem is better understood for planar graphs as compared to general graphs. For example, deterministic NC-algorithms for the problem are known for planar graphs, but no such algorithm is known for general graphs. A common approach to reduce a graph problem to the planar case is to use planarizing gadgets. Our main contribution is to show that, unconditionally, planarizing gadgets for the problem of recognizing (k, l)-tight graphs do not exist.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves no planarizing gadgets exist for (k,l)-tight graph recognition, a clean negative result that blocks one reduction route but turns on how the gadget is defined.

read the letter

The main point is that planarizing gadgets cannot exist for recognizing (k, l)-tight graphs. This stops a standard trick for turning general instances into planar ones while keeping the same yes/no answer on tightness. The result is unconditional, which is the central new claim. Earlier work already had deterministic NC algorithms for the planar case, so this explains why those techniques do not lift directly. The authors link the problem to rigidity theory, which fits the setting and gives the right context for why the property is hard to localize. The proof works by assuming a gadget that replaces a non-planar subgraph with a planar one and then showing that it cannot preserve exact membership in the (k, l)-tight class or its complement. That argument looks internally consistent on the terms given in the abstract. The paper does a reasonable job of spelling out what the gadget must achieve: it has to work for arbitrary graphs and keep the global tightness property intact. One soft spot is the scope of the gadget definition itself. If a reduction could use auxiliary vertices whose degrees are fixed later, or could preserve only the existence of a tight spanning subgraph rather than the whole graph, or could overlap several replacements, then the impossibility might not apply. The stress-test note flags exactly this issue, and the paper's claim stands or falls on whether its formal definition in section 2 is the most general one that still counts as a valid Karp reduction. From the abstract alone the definition seems standard, but a referee would want to check that no broader gadget form sneaks through. This paper is for people working on graph algorithms for rigidity or matroid problems who are looking for ways to exploit planarity. It is a useful clarification of a dead end rather than a positive algorithm. I would send it to peer review; the negative result is sharp enough in the subfield to merit referee time, even if the gadget definition needs a bit more justification.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that planarizing gadgets for recognizing (k, l)-tight graphs do not exist. It defines a planarizing gadget as a local replacement that turns a non-planar subgraph into a planar one while exactly preserving membership (or non-membership) in the (k, l)-tight class, then shows that no such gadget can exist by deriving a contradiction with known combinatorial properties of (k, l)-tight graphs and the fact that planar recognition admits deterministic NC algorithms while the general case does not.

Significance. If the non-existence result holds under the stated definition, it is significant: it rules out the standard gadget-based Karp reduction from general to planar instances for this sparsity problem, which is closely tied to graph rigidity and matroid parity. The result therefore explains the current algorithmic separation between the planar and general cases and indicates that new techniques (beyond local planarizing replacements) will be required to obtain NC or other efficient algorithms for general (k, l)-tight graphs.

major comments (2)

[§2] §2 (Definition of planarizing gadget): the chosen definition requires that the gadget exactly preserves (k, l)-tightness of the entire graph after replacement. This is load-bearing for the unconditional non-existence claim, yet it is not shown to be the most general notion that still yields a valid Karp reduction; reductions that preserve only the existence of a (k, l)-tight spanning subgraph, permit auxiliary vertices whose degrees are adjusted globally, or compose overlapping replacements are not ruled out by the argument.
[§3] §3 (Proof of non-existence): the contradiction is derived from the assumption that a single local replacement suffices. It is unclear whether the argument extends to multi-gadget or non-local reductions that might still map general instances to planar ones while preserving the decision problem; a concrete counter-example construction or a lemma showing that any valid reduction must be local would strengthen the claim.

minor comments (2)

The introduction could explicitly compare the chosen gadget definition to those used in prior non-existence results for other problems (e.g., planarizing gadgets for 3-coloring or Hamiltonicity) to clarify why the same technique fails here.
Notation for (k, l)-tightness and the precise parameters of the gadget (number of attachment points, degree sequence) should be summarized in a single table or figure for quick reference.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and indicate the revisions we will make.

read point-by-point responses

Referee: [§2] §2 (Definition of planarizing gadget): the chosen definition requires that the gadget exactly preserves (k, l)-tightness of the entire graph after replacement. This is load-bearing for the unconditional non-existence claim, yet it is not shown to be the most general notion that still yields a valid Karp reduction; reductions that preserve only the existence of a (k, l)-tight spanning subgraph, permit auxiliary vertices whose degrees are adjusted globally, or compose overlapping replacements are not ruled out by the argument.

Authors: Our definition formalizes the standard local replacement used in gadget reductions for decision problems on graph properties: a fixed planar graph fragment is substituted for a non-planar subgraph so that the whole graph remains (k, l)-tight if and only if the original was. This directly yields a Karp reduction from general to planar instances. Reductions that preserve only the existence of a (k, l)-tight spanning subgraph address a different problem; the recognition task we study asks whether the input graph itself satisfies the tightness conditions. Global degree adjustments or overlapping replacements likewise fall outside the local-gadget paradigm that the term “planarizing gadget” conventionally denotes. We will add a short clarifying paragraph in §2 explaining why the chosen definition suffices to rule out the usual gadget-based approach for this sparsity problem. revision: yes
Referee: [§3] §3 (Proof of non-existence): the contradiction is derived from the assumption that a single local replacement suffices. It is unclear whether the argument extends to multi-gadget or non-local reductions that might still map general instances to planar ones while preserving the decision problem; a concrete counter-example construction or a lemma showing that any valid reduction must be local would strengthen the claim.

Authors: The contradiction in §3 relies on the local combinatorial obstructions that any single planarizing replacement would have to satisfy, together with the known NC separation between the planar and general cases. The argument does not automatically extend to compositions of multiple gadgets or to non-local transformations, because interactions among several replacements could evade the local obstructions we derive. We currently lack both a concrete counter-example showing that every valid reduction must be local and a general lemma to that effect. We will therefore revise the concluding section to state explicitly that the non-existence result applies to local gadgets—the standard technique for planarizing reductions—and to note that more general reductions remain open. revision: partial

standing simulated objections not resolved

Whether the non-existence result extends to multi-gadget or non-local reductions that preserve the decision problem.

Circularity Check

0 steps flagged

Non-existence proof is a direct mathematical argument with no self-referential reduction.

full rationale

The paper establishes an unconditional non-existence result for planarizing gadgets in (k,l)-tight graph recognition. This is achieved through a formal proof that applies the stated definitions of gadgets and tightness to show impossibility, drawing on external graph-theoretic concepts rather than any fitted parameters, renamed empirical patterns, or self-citation chains that would make the conclusion tautological. No step in the derivation reduces by construction to the inputs; the argument remains independent and falsifiable against the chosen definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on standard definitions from rigidity theory and the precise notion of planarizing gadgets; no free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Standard definition of (k, l)-tight graphs from combinatorial rigidity
The recognition problem is defined in terms of this property.
domain assumption Formal definition of what constitutes a planarizing gadget and the properties it must preserve
Central to proving that no such gadget can exist.

pith-pipeline@v0.9.0 · 5404 in / 1193 out tokens · 36518 ms · 2026-05-11T02:28:54.354621+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

125 extracted references · 125 canonical work pages

[1]

arXiv: Combinatorics , year=

Pseudo-Triangulations - a Survey , author=. arXiv: Combinatorics , year=

work page
[2]

Planar minimally rigid graphs and pseudo-triangulations , journal=

Haas, Ruth and Orden, David and Rote, Günter and Santos, Francisco and Servatius, Brigitte and Servatius, Hermann and Souvaine, Diane and Streinu, Ileana and Whiteley, Walter , year=. Planar minimally rigid graphs and pseudo-triangulations , journal=

work page
[3]

1996 , month = dec, publisher =

C Moukarzel , title =. 1996 , month = dec, publisher =

work page 1996
[4]

27th Annual European Symposium on Algorithms (ESA) , pages =

Rollin, Jonathan and Schlipf, Lena and Schulz, Andr\'. 27th Annual European Symposium on Algorithms (ESA) , pages =. 2019 , volume =

work page 2019
[5]

2005 , month = sep, publisher =

Ileana Streinu , title =. 2005 , month = sep, publisher =

work page 2005
[6]

Miller and Joseph Naor , title =

Gary L. Miller and Joseph Naor , title =. 1995 , month = oct, publisher =

work page 1995
[7]

Proceedings of the forty-sixth annual

Michael Elberfeld and Ken-ichi Kawarabayashi , title =. Proceedings of the forty-sixth annual. 2014 , month = may, publisher =

work page 2014
[8]

1989 , month = sep, publisher =

Michael T Goodrich , title =. 1989 , month = sep, publisher =

work page 1989
[9]

1992 , month = feb, publisher =

Bruce Hendrickson , title =. 1992 , month = feb, publisher =

work page 1992
[10]

Proceedings of the forty-eighth annual

Stephen Fenner and Rohit Gurjar and Thomas Thierauf , title =. Proceedings of the forty-eighth annual. 2016 , month = jun, publisher =

work page 2016
[11]

Vazirani , title =

Nima Anari and Vijay V. Vazirani , title =. 59th Annual Symposium on Foundations of Computer Science (. 2018 , publisher =

work page 2018
[12]

, title =

Anari, Nima and Vazirani, Vijay V. , title =. 2020 , issue_date =. doi:10.1145/3397504 , journal =

work page doi:10.1145/3397504 2020
[13]

Varadarajan , title =

Meena Mahajan and Kasturi R. Varadarajan , title =. 32nd. 2000 , publisher =

work page 2000
[14]

2009 , publisher =

Samir Datta and Raghav Kulkarni and Sambuddha Roy , title =. 2009 , publisher =

work page 2009
[15]

Vinodchandran , title =

Raghunath Tewari and N.V. Vinodchandran , title =. 2012 , month = jun, publisher =

work page 2012
[16]

Tay, Tiong-Seng and Whiteley, Walter , year =

work page
[17]

A proof of Connelly

Alex R Berg and Tibor Jord. A proof of Connelly. 2003 , month = may, publisher =

work page 2003
[18]

Tutte , title =

William T. Tutte , title =. 1961 , publisher =

work page 1961
[19]

Crispin St. J. A. Nash-Williams , title =. 1961 , publisher =

work page 1961
[20]

C. St.J. A. Nash-Williams , title =. 1964 , publisher =

work page 1964
[21]

2010 , month = aug, publisher =

Haim Kaplan and Yahav Nussbaum , title =. 2010 , month = aug, publisher =

work page 2010
[22]

Good orientations of unions of edge-disjoint spanning trees , journal =

J. Good orientations of unions of edge-disjoint spanning trees , journal =. 2020 , month = oct, publisher =

work page 2020
[23]

2007 , month = feb, publisher =

David Orden and Francisco Santos and Brigitte Servatius and Herman Servatius , title =. 2007 , month = feb, publisher =

work page 2007
[24]

Klein and John H

Philip N. Klein and John H. Reif , title =. 1988 , month = oct, publisher =

work page 1988
[25]

Matroid Theory , publisher =

Walter Whiteley , title =. Matroid Theory , publisher =. 1996 , pages =

work page 1996
[26]

2023 , copyright =

Datta, Samir and Khan, Asif and Mukherjee, Anish , title =. 2023 , copyright =

work page 2023
[27]

2007 , publisher =

Walter, Dominic and Husty, Manfred , title =. 2007 , publisher =

work page 2007
[28]

1976 , author =

On deformable nine-bar linkages with six triple joints , journal =. 1976 , author =

work page 1976
[29]

, year =

Holmes‐Cerfon, Miranda and Theran, Louis and Gortler, Steven J. , year =. Almost Rigidity of Frameworks , volume =. Communications on Pure and Applied Mathematics , publisher =

work page
[30]

1985 , author =

An approach to the subgraph homeomorphism problem , journal =. 1985 , author =

work page 1985
[31]

ACM Trans

Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian , title =. ACM Trans. Comput. Theory , month =. 2022 , issue_date =

work page 2022
[32]

, year =

Wagner, K. , year =. \". Mathematische Annalen , publisher =

work page
[33]

The design and analysis of algorithms

Kozen, Dexter. The design and analysis of algorithms

work page
[34]

The Polytope of Non-Crossing Graphs on a Planar Point Set , volume =

Orden, David and Santos, Francisco , year =. The Polytope of Non-Crossing Graphs on a Planar Point Set , volume =. Discrete & Computational Geometry , publisher =

work page
[35]

Journal of the ACM , articleno =

Reingold, Omer , title =. Journal of the ACM , articleno =. 2008 , issue_date =

work page 2008
[36]

, title =

Han, Yujie and Wagner, Robert A. , title =. J. ACM , month =. 1990 , issue_date =

work page 1990
[37]

and Ramachandran, Vijaya , year =

Miller, Gary L. and Ramachandran, Vijaya , year =. A new graph triconnectivity algorithm and its parallelization , volume =. Combinatorica , publisher =

work page
[38]

Crapo, Henry , TYPE =

work page
[39]

and Westermann, Herbert H

Gabow, Harold N. and Westermann, Herbert H. , year =. Forests, frames, and games: Algorithms for matroid sums and applications , volume =. Algorithmica , publisher =

work page
[40]

Extremal Graphs Having No Stable Cutset , volume =

Le, Van Bang and Pfender, Florian , year =. Extremal Graphs Having No Stable Cutset , volume =. The Electronic Journal of Combinatorics , publisher =

work page
[41]

Counting the Number of Perfect Matchings in

Straub, Simon and Thierauf, Thomas and Wagner, Fabian , booktitle=. Counting the Number of Perfect Matchings in. 2014 , volume=

work page 2014
[42]

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , pages =

Datta, Samir and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian , title =. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , pages =. 2009 , volume =

work page 2009
[43]

Acta Universitatis Szegediensis Sect

On straight line representation of planar graphs , pages =. Acta Universitatis Szegediensis Sect. Sci. Math.11 , author =

work page
[44]

Parallel construction of canonical ordering and convex drawing of triconnected planar graphs , ISBN =

He, Xin and Kao, Ming-Yang , year =. Parallel construction of canonical ordering and convex drawing of triconnected planar graphs , ISBN =. Algorithms and Computation , publisher =

work page
[45]

, year =

Pollaczek‐Geiringer, H. , year =. Journal of Applied Mathematics and Mechanics , publisher =

work page
[46]

On graphs and rigidity of plane skeletal structures , volume =

Laman, Gerard , year =. On graphs and rigidity of plane skeletal structures , volume =. Journal of Engineering Mathematics , publisher =

work page
[47]

2005 , issn =

Rigid realizations of graphs on small grids , journal =. 2005 , issn =

work page 2005
[48]

Handbook of Discrete and Computational Geometry (3rd ed.) , publisher =

work page
[49]

Graph Theory , ISBN =

Diestel, Reinhard , year =. Graph Theory , ISBN =. Graduate Texts in Mathematics , publisher =

work page
[50]

Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing , pages =

Pan, V and Reif, J , title =. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing , pages =. 1985 , isbn =

work page 1985
[51]

Journal of Computer and System Sciences , volume =

Connected Components in. Journal of Computer and System Sciences , volume =. 1997 , issn =

work page 1997
[52]

Pacific Journal of Mathematics , number =

Walter Whiteley , title =. Pacific Journal of Mathematics , number =

work page
[53]

A fast parallel algorithm to compute the rank of a matrix over an arbitrary field , volume =

Mulmuley, Ketan , year =. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field , volume =. Combinatorica , publisher =

work page
[54]

1979 , issn =

The rigidity of graphs, II , journal =. 1979 , issn =

work page 1979
[55]

, journal =

Wagner, K. , journal =. Bemerkungen zum Vierfarbenproblem. , volume =

work page
[56]

, journal =

Euler, L. , journal =. Euler Archive index number E819 , volume =

work page
[57]

Abbot, T. G. , title =. 2008 , note =

work page 2008
[58]

Bill Jackson , title =

work page
[59]

Operator Scaling: Theory and Applications , volume =

Garg, Ankit and Gurvits, Leonid and Oliveira, Rafael and Wigderson, Avi , year =. Operator Scaling: Theory and Applications , volume =. Foundations of Computational Mathematics , publisher =

work page
[60]

Schwartz, J. T. , title =. 1980 , issue_date =. doi:10.1145/322217.322225 , journal =

work page doi:10.1145/322217.322225 1980
[61]

Probabilistic algorithms for sparse polynomials

Zippel, Richard. Probabilistic algorithms for sparse polynomials. Symbolic and Algebraic Computation. 1979

work page 1979
[62]

and Demaine, Martin L

Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lynch, Jayson and Schardl, Tao B. , title =. 32nd International Symposium on Computational Geometry (SoCG 2016) , pages =. 2016 , volume =. doi:10.4230/LIPIcs.SoCG.2016.3 , annote =

work page doi:10.4230/lipics.socg.2016.3 2016
[63]

2025 , pages=

Journal of Computational Geometry , author=. 2025 , pages=

work page 2025
[64]

2017 , volume =

Svensson, Ola and Tarnawski, Jakub , booktitle =. 2017 , volume =. doi:10.1109/FOCS.2017.70 , url =

work page doi:10.1109/focs.2017.70 2017
[65]

and Wigderson, Avi , title=

Raz, Orit E. and Wigderson, Avi , title=. Building Bridges II: Mathematics of L. 2019 , publisher=

work page 2019
[66]

Flats in matroids and geometric graphs , journal =

László, Lovász , year =. Flats in matroids and geometric graphs , journal =

work page
[67]

Reachability in K_ 3,3 -free G raphs and K_5 - free Graphs is in Unambiguous Logspace

Thierauf, Thomas and Wagner,Fabian. Reachability in K_ 3,3 -free G raphs and K_5 - free Graphs is in Unambiguous Logspace. Chicago Journal of Theoretical Computer Science. 2014

work page 2014
[68]

Extending planar graph algorithms to

Samir Khuller , abstract =. Extending planar graph algorithms to. Information and Computation , volume =. 1990 , issn =. doi:https://doi.org/10.1016/0890-5401(90)90031-C , url =

work page doi:10.1016/0890-5401(90)90031-c 1990
[69]

Coloring algorithms for

Samir Khuller , keywords =. Coloring algorithms for. Information Processing Letters , volume =. 1990 , issn =. doi:https://doi.org/10.1016/0020-0190(90)90161-P , url =

work page doi:10.1016/0020-0190(90)90161-p 1990
[70]

1989 , issn =

Information and Computation , volume =. 1989 , issn =. doi:https://doi.org/10.1016/0890-5401(89)90017-5 , url =

work page doi:10.1016/0890-5401(89)90017-5 1989
[71]

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) , pages =

Arora, Rahul and Gupta, Ashu and Gurjar, Rohit and Tewari, Raghunath , title =. 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) , pages =. 2016 , volume =. doi:10.4230/LIPIcs.STACS.2016.10 , annote =

work page doi:10.4230/lipics.stacs.2016.10 2016
[72]

49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) , pages =

Chauhan, Archit and Datta, Samir and Gupta, Chetan and Sharma, Vimal Raj , title =. 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.MFCS.2024.43 , annote =

work page doi:10.4230/lipics.mfcs.2024.43 2024
[73]

Flows in One-Crossing-Minor-Free Graphs

Chambers, Erin and Eppstein, David. Flows in One-Crossing-Minor-Free Graphs. Algorithms and Computation. 2010

work page 2010
[74]

and Hajiaghayi, MohammadTaghi and Thilikos, Dimitrios M

Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Thilikos, Dimitrios M. 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor. Approximation Algorithms for Combinatorial Optimization. 2002

work page 2002
[75]

Hall , title =

P. Hall , title =. Journal of the London Mathematical Society , volume =

work page
[76]

Journal de l'École polytechnique , pages =

Augustin-Louis Cauchy , title =. Journal de l'École polytechnique , pages =

work page
[77]

John Robert Edmonds , title =. Not. Am. Math. Soc. , pages =. 1960 , volume =

work page 1960
[78]

Planarity testing in parallel , journal =

Vijaya Ramachandran and John Reif , abstract =. Planarity testing in parallel , journal =. 1994 , note =. doi:https://doi.org/10.1016/S0022-0000(05)80070-4 , url =

work page doi:10.1016/s0022-0000(05)80070-4 1994
[79]

Graphs and Combinatorics , year=

Tay, Tiong-Seng , title=. Graphs and Combinatorics , year=. doi:10.1007/BF02988323 , url=

work page doi:10.1007/bf02988323
[80]

Note On Finding Minimum-cost Edge-Disjoint Spanning Trees

James Roskind and Tarjan, Robert E. Note On Finding Minimum-cost Edge-Disjoint Spanning Trees. Mathematics of Operations Research. 1985

work page 1985

Showing first 80 references.