Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs

Emilio Di Giacomo; Fabrizio Montecchiani; Giuseppe Liotta

REVIEW 3 major objections 4 minor 30 references

Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Fixed treewidth makes orthogonal planarity polynomial

desk verdict Strong FPT/XP result for bounded-treewidth OrthogonalPlanarity with a real series-parallel improvement, but the central correctness lemma is asserted without proof. read the letter →

arxiv 1908.05015 v1 pith:CMXEDMPD submitted 2019-08-14 cs.CG cs.DS

Emilio Di Giacomo , Giuseppe Liotta , Fabrizio Montecchiani This is my paper · ORCID

classification cs.CGcs.DS MSC 68R1005C8568Q2568U05

keywords orthogonalplanaritytreewidthfixed-parametertractablealgorithmssketchesbendminimizationHV-planarityseries-parallelgraphsFlexDraw

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

OrthogonalPlanarity asks whether a planar graph can be drawn with axis-parallel edges and at most $b$ bends in total; it is NP-complete even when $b=0$. This paper claims that bounded treewidth removes the hardness: it gives an algorithm that decides the problem in $f(k,\sigma,b)\cdot n$ time, where $k$ is the treewidth, $\sigma$ the number of degree-2 vertices, and $b$ the bend budget. The method replaces full drawings by orthogonal sketches, one per bag of a tree-decomposition, so that only the shape of a drawing on the bag's active vertices is remembered. If the algorithm's merge step is correct, OrthogonalPlanarity is polynomial for every fixed treewidth, runs in $O(n^3\log n)$ for series-parallel graphs, and the same sketches decide HV-Planarity and FlexDraw on bounded-treewidth inputs.

What carries the argument

An orthogonal sketch is a sketched embedding together with a shape. The sketched embedding keeps only the representing cycles of faces that contain active vertices: oriented cycles through the active vertices in their boundary order. The shape assigns to each dart of the sketch a vertex-angle value $\varphi$ and a roll-up number $\rho$, an integer that records how the face winds between consecutive active vertices by counting right turns against left turns along the corresponding boundary path. Lemma 2 is the balance law every cycle must satisfy, and Lemma 3 bounds the number of distinct sketches by $w^{O(w)}(\sigma+b)^{w-1}$ for a bag of size $w$, because only $w-1$ roll-up numbers can be chosen freely once vertex angles are fixed. This state-space bound is what keeps the dynamic program's per-bag work within $k^{O(k)}(\sigma+b)^k\log(\sigma+b)$.

What would settle it

Run OrthoPlanTester and a brute-force enumeration of all orthogonal representations with at most $b$ bends on the same small series-parallel graphs, up to about ten vertices, focusing on graphs built by joining two components along a shared set of boundary vertices. A graph where the algorithm answers yes but no drawing exists would disprove the merge step; the natural place to look is a pair of shape-compatible sketches whose merged angle assignment violates the face balance law or forces a vertex angle sum greater than $2\pi$, since those are the only conditions the merge checks.

Watch

Extended reading notes

Core claim

The central discovery is a dynamic program over a nice tree-decomposition whose states are shape-equivalence classes of orthogonal representations, called orthogonal sketches. Two representations are equivalent when they have the same sketched embedding on the active vertices and the same shape functions $\varphi$ and $\rho$; the paper bounds the number of such classes by $k^{O(k)}(\sigma+b)^{k-1}$. Theorem 1 states that OrthogonalPlanarity with budget $b$ is decidable in $k^{O(k)}(\sigma+b)^k \log(\sigma+b)\cdot n$ time given a width-$k$ decomposition. Corollary 1 then observes that both $\sigma$ and $b$ are $O(n)$, so the problem is decidable in $k^{O(k)}n^{k+1}\log n$ time and a bend-minimum drawing can be found in $k^{O(k)}n^{k+1}\log^2 n$ time. For treewidth 2 this gives $O(n^3\log n)$ decision and $O(n^3\log^2 n)$ bend minimization, without the biconnectivity restriction of the previous $O(n^4)$ series-parallel algorithm, and the same machinery gives $O(n^3\log n)$ HV-Planarity for series-parallel graphs.

Load-bearing premise

The load-bearing premise is the join step: the algorithm assumes that any two partial drawings encoded by sketches that agree on the shared boundary vertices and whose combined bend count fits the budget can always be merged into a valid drawing of the whole graph. This step is asserted in Lemma 4 without proof.

Editorial extensions

If this is right

For every fixed treewidth $k$, OrthogonalPlanarity is decidable in polynomial time, placing the problem in XP when parameterized by treewidth.
Series-parallel graphs, which have treewidth 2, get $O(n^3\log n)$ decision and $O(n^3\log^2 n)$ bend minimization, improving the previous $O(n^4)$ bound and dropping its biconnectivity restriction.
HV-Planarity is decidable in $O(n^3\log n)$ for series-parallel graphs, improving the previous $O(n^4)$ algorithm for that class.
FlexDraw is solvable in polynomial time for bounded-treewidth graphs by subdividing each edge $\psi(e)$ times and then testing a bendless drawing.
The algorithm is constructive: on a positive answer it outputs an orthogonal drawing, and a binary search on the budget $b$ yields a bend-minimum drawing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the missing proof of Lemma 4 is supplied, the sketch framework should transfer to other drawing conventions whose validity is a conjunction of local vertex and face conditions, such as octilinear drawings or drawings with prescribed edge directions; the paper does not pursue this.
The explicit dependence on the number $\sigma$ of degree-2 vertices suggests that long chains of degree-2 vertices are what make the state space grow; contracting maximal degree-2 paths and remembering only their lengths might reduce the bound, but the paper does not claim this.
Because the merge step is unproved in this version, the series-parallel speedups should be read as conditional on that lemma; finding a counterexample would not kill the sketch idea but would force a stronger compatibility test at join nodes.
The XP bound $k^{O(k)}n^{k+1}\log n$ leaves open whether OrthogonalPlanarity is FPT when parameterized by treewidth and bend budget alone; the authors explicitly raise this as an open problem.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The headline: a genuinely useful FPT/XP result for OrthogonalPlanarity on bounded-treewidth graphs, with a concrete improvement for series-parallel graphs, but the paper as written has a load-bearing proof gap at the join step.

What's new: the orthogonal sketch abstraction is a natural and clever way to compress the relevant set of orthogonal representations into finitely many equivalence classes. It yields the first polynomial-time algorithm for fixed treewidth (Corollary 1) and O(n^3 log n) time for series-parallel graphs, beating the old O(n^4) bound. The extensions to HV-Planarity and FlexDraw are plausible and follow from the same machinery. Lemmas 1–3 in the appendix are argued in detail, and the counting bounds look right.

The soft spot, and it is not minor: Lemma 4, which states the algorithm is correct, is asserted without proof. Section 4 ends the join-node description with 'We conclude: Lemma 4.' There is no argument anywhere in the paper. The join phase checks that two sketched embeddings, after adding dummy vertices, admit a common planar embedding compatible with the children, and that shapes exist whose restrictions match the child sketches and whose bend counts fit the budget. What is not shown is that these local conditions are sufficient for the existence of an actual orthogonal representation of the union graph. Sketched embeddings discard forgotten vertices and internal face structure, so the checks may miss global constraints. If Lemma 4 is false, the algorithm could accept graphs that have no valid orthogonal drawing, invalidating Theorem 1 and Corollary 1. Lemma 5, the runtime bound, is also a sketch, but it's the kind of thing that can be checked line by line; the missing correctness proof is the real issue.

This is not a takedown: the core idea has legs, and the missing lemma might be provable. The counting lemmas suggest the authors worked through substantial detail. But as submitted, the main theorem is not backed by a complete correctness argument. A careful referee should ask for a full proof of Lemma 4, ideally with a more detailed join-phase argument.

Who this is for: people working on parameterized complexity of graph drawing, especially orthogonal representations and treewidth. They should read it, with the caveat above.

Recommendation: send it to peer review, with the expectation that the authors supply a complete proof of Lemma 4. A desk reject would be wrong; the result is important enough to give them the chance.

Best.

Referee Report

3 major / 4 minor

Summary. The paper introduces the notion of an orthogonal sketch, an equivalence class of orthogonal representations of a graph with respect to an active vertex set, and uses it in a bottom-up dynamic program over a nice tree-decomposition to decide OrthogonalPlanarity. The main algorithmic claim (Theorem 1) is an f(k,σ,b)·n-time decision procedure for n-vertex planar graphs of maximum degree four, where k is the treewidth, σ is the number of degree-2 vertices, and b is the bend budget; Corollary 1 derives k^{O(k)} n^{k+1} log n time when parameterized by treewidth alone. The paper further claims extensions to HV-Planarity and FlexDraw, including an O(n^3 log n) algorithm for series-parallel graphs. The central correctness statement is Lemma 4, which asserts that the dynamic program accepts exactly the graphs admitting an orthogonal drawing with at most b bends.

Significance. If the results are correct, they place OrthogonalPlanarity in XP for bounded treewidth, improve the best known bound for series-parallel graphs from O(n^4) to O(n^3 log n), and provide a uniform framework covering HV-Planarity and FlexDraw. The orthogonal sketch abstraction is natural, and the counting arguments in Lemmas 1–3 are detailed and largely plausible. However, the load-bearing correctness lemma for the join operation (Lemma 4) is stated without proof, and the bend-accounting in the dynamic program conflates a signed roll-up number with a bend count. These gaps must be resolved before the main claims are established.

major comments (3)

[Section 4, join node (ending 'We conclude: Lemma 4')] Lemma 4 is the if-and-only-if correctness statement for the whole algorithm, but it is asserted without proof; the appendix supplies only the missing part of the runtime proof of Lemma 5. The join phase combines local checks — planarity of the union of connected sketched embeddings compatible with the child embeddings, face-orientation consistency, existence of restricting shapes in Bj and Bj′, and the bend budget — but no argument shows that these local conditions are sufficient to guarantee an orthogonal representation of Gi satisfying Definition 1, nor that every valid representation of Gi yields sketches that pass the checks. Since Theorem 1 and Corollary 1 rest entirely on Lemma 4, this is a load-bearing gap that must be closed with a full proof, including the cases of disconnected graphs and vertices appearing multiple times on a face boundary.
[Section 3 and Section 4, join phase 1] The algorithm computes 'a' connected sketched embedding for each child sketch, but Section 3 states that different connected sketched embeddings of the same sketched embedding may exist, and the subsequent planarity test of the union C depends on the dummy vertices and edges added. An arbitrary choice could reject a valid merge or accept an invalid one. The assertion that 'any connected sketched embedding encodes the information about the global structure of H that is sufficient' is not proved. The algorithm must either enumerate all relevant choices or prove an invariance lemma showing that the choice does not affect the ability to detect a valid glued representation.
[Section 4, introduce-vertex and join bend checks] The text says 'ρ(v,ui) corresponds to the number of bends along the edge (v,ui)' and later uses '|ρ(u,v)|' as the number of bends along shared edges in Ei. By the definition in Section 3, ρ is a signed net turn (n_{π/2} − n_{3π/2} − 2n_{2π}), not a bend count. A single edge with one 90° and one 270° bend has ρ = 0 on each dart but contains two bends, so |ρ| undercounts the bend count unless an unstated normalization to bend-minimal representatives is assumed. Since the bend budget is central to the decision procedure, the paper must either prove that in a bend-minimal representation within a shape class every edge path has all bends in the same direction, or maintain additional information to compute the true accumulated bend count; the introduce-phase inequality should also use absolute values (or the correct formula) if negative roll-up numbers are permitted.

minor comments (4)

[Appendix B, Lemma 5 missing part] There is a missing space in 'algorithmOrthoPlanTester' that should read 'algorithm OrthoPlanTester'.
[Appendix A, Lemma 3 proof] The phrase '2n′2π(f)' appears to be a typo; it should presumably read 'n′2π(f)'.
[Section 4, forget-vertex case] The condition 'If v is the only vertex of Cf' is ambiguous when v occurs multiple times on the closed walk of a representing cycle; please clarify that it means v is the only distinct vertex on the cycle, or describe how to handle each occurrence separately.
[Section 5, Theorem 3] The symbol b* is used both as the maximum edge weight in FlexDraw and in the runtime bound; consider defining it in the theorem statement for readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithm is self-contained and checked against Tamassia's external orthogonal-representation characterization.

full rationale

The paper derives its FPT algorithm from a formally defined data structure (orthogonal sketches) and checks its output against the external combinatorial characterization of orthogonal drawings in Definition 1, which is taken from Tamassia ([29]) and the textbook [12]; no parameter is fitted to the target answer, and no conclusion is assumed as input. The equivalence-class bounds in Lemmas 1 and 3 are obtained by constructive encoding and counting arguments, and the dynamic program enumerates sketches rather than deriving the answer from a precomputed value. The only self-citations are background results and are not load-bearing for Theorem 1. The main gap noted in the manuscript, Lemma 4, is stated without proof, and its join-step conditions are a genuine correctness obligation rather than a circular definition; a false positive there would invalidate the theorem, but that would be an unproved lemma, not a reduction of the theorem to its own inputs. Accordingly, no circular step can be exhibited by quoting equations that reduce to themselves.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard prior results (Tamassia's characterization, nice tree-decompositions, bend bound) and on the paper's own orthogonal sketch definition. There are no fitted parameters. No invented physical entities.

assumptions (4)

domain assumption Tamassia's characterization: an orthogonal drawing exists iff there is a planar embedding and angle assignment satisfying conditions C1 to C3 (Definition 1).
Used in Section 2 as the foundation; this is a prior result from [29].
standard math Nice tree-decompositions of width k exist and can be computed in polynomial time for fixed k.
Invoked in Section 2 from [26]; standard in parameterized algorithms.
domain assumption Every orthogonal representation can be realized as a drawing in O(n) time (Tamassia's theorem).
Used at the end of Section 4 to reconstruct a drawing from a representation.
domain assumption A bend-minimum orthogonal drawing of an n-vertex planar graph has O(n) bends.
Used in Corollary 1 for binary search on b; cited to [3].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs." pith.science (2026). https://pith.science/paper/CMXEDMPD

@misc{pith2026190805015,
  author       = {Pith},
  title        = {Pith review of: Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CMXEDMPD}},
  note         = {Machine review of arXiv:1908.05015}
}

abstract

Given a planar graph $G$ and an integer $b$, OrthogonalPlanarity is the problem of deciding whether $G$ admits an orthogonal drawing with at most $b$ bends in total. We show that OrthogonalPlanarity can be solved in polynomial time if $G$ has bounded treewidth. Our proof is based on an FPT algorithm whose parameters are the number of bends, the treewidth and the number of degree-2 vertices of $G$. This result is based on the concept of sketched orthogonal representation that synthetically describes a family of equivalent orthogonal representations. Our approach can be extended to related problems such as HV-Planarity and FlexDraw. In particular, both OrthogonalPlanarity and HV-Planarity can be decided in $O(n^3 \log n)$ time for series-parallel graphs, which improves over the previously known $O(n^4)$ bounds.

Figures

Figures reproduced from arXiv: 1908.05015 by the authors.

**Figure 1.** (a) An orthogonal drawing Γ of a graph G = (V, E) with 8 bends; the white vertices define a set X ⊆ V . (b) The representing cycles of the active faces of H with respect to X, where H denotes the orthogonal representation of Γ. (c) The connected sketched embedding C ∗ (H, G). (d) The orthogonal sketch hC(H, X), φ, ρi. 3 Orthogonal Sketches Recall that an orthogonal representation of a planar graph G corresponds to a… view at source ↗

**Figure 2.** A portion of a orthogonal sketch before and after removing the bigger vertices. from Cf . It is immediate to verify that Lemma 2 holds for Cf after applying this operation. See Figs. 2a and 2b for an illustration. The above operation does not change the number of bends associated with the resulting orthogonal sketches, but it may create duplicated orthogonal sketches for Bi , which we delete. When deleting the dupli… view at source ↗

**Figure 3.** (a) For each 2π angle there exist two π 2 angles. (b) An orthogonal representation of the largest component of the sketched embedding of [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Two portions of two different orthogonal sketches with one and two bends, respectively. When the bigger vertex is removed, they will give rise to two orthogonal sketches that are the same but have a different number of bends. (a) v (b) (c) v (d) [PITH_FULL_IMAGE:figur…

**Figure 5.** Figure 5: Extending a disconnected orthogonal representation with an introduced vertex v. Vertex v and its neighbors are shown in white. (a)–(b) There exists an inner face containing a neighbor of v; (c)–(d) No internal face contains a neighbor of v [PITH_FULL_IMAGE:figures/ful…

**Figure 6.** Figure 6: Merging two orthogonal representations sharing a cutset X. Vertices in X are shown in white. (a)–(b) A rectilinear representation H1 and its connected sketched embedding C ∗ (H1, X) with the shape corresponding to H1. (c)–(d) A rectilinear representation H2 and its co…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 27 canonical work pages

[1]

Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complex- ity of 1-planarity. J. Graph Algorithms Appl. 22(1), 23–49 (2018). https://doi.org/10.7155/jgaa.00457

doi:10.7155/jgaa.00457 2018
[2]

Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page draw- ings of graphs with bounded treewidth. J. Graph Algorithms Appl. 22(4), 577–606 (2018). https://doi.org/10.7155/jgaa.00479

doi:10.7155/jgaa.00479 2018
[3]

Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998)

work page 1998
[4]

ACM Trans

Biedl, T.C., Lubiw, A., Petrick, M., Spriggs, M.J.: Morphing orthogonal planar graph drawings. ACM Trans. Algorithms 9(4), 29:1–29:24 (2013)

work page 2013
[5]

Algorithmica 68(4), 859–885 (2014)

Bl¨ asius, T., Krug, M., Rutter, I., Wagner, D.: Orthogonal graph drawing with ﬂexibility constraints. Algorithmica 68(4), 859–885 (2014)

work page 2014
[6]

Bl¨ asius, T., Lehmann, S., Rutter, I.: Orthogonal graph drawing with inﬂexible edges. Comput. Geom. 55, 26–40 (2016)

work page 2016
[7]

Bodlaender, H.L.: A linear-time algorithm for ﬁnding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)

work page 1996
[8]

In: IPEC 2013

Bodlaender, H.L., Bonsma, P.S., Lokshtanov, D.: The ﬁne details of fast dynamic programming over tree decompositions. In: IPEC 2013. LNCS, vol. 8246, pp. 41–53. Springer (2013)

work page 2013

Show all 30 references

[9]

Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A c k n 5-approximation algorithm for treewidth. SIAM J. Com- put. 45(2), 317–378 (2016)

2016
[10]

In: Albers, S., Radzik, T

Chan, H.Y.: A parameterized algorithm for upward planarity testing. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 157–168. Springer (2004). https://doi.org/10.1007/978-3-540-30140-0 16

2004 doi
[11]

In: SOCG 2017

Chang, Y., Yen, H.: On bend-minimized orthogonal drawings of planar 3-graphs. In: SOCG 2017. LIPIcs, vol. 77, pp. 29:1–29:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)

2017
[12]

Prentice-Hall (1999)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall (1999)

1999
[13]

Di Battista, G., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 1764–1811 (1998)

1998
[14]

Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. Discrete Math. 23(4), 1842–1899 (2009). https://doi.org/10.1137/070696854

2009 doi
[15]

In: ISAAC 1998

Didimo, W., Liotta, G.: Computing orthogonal drawings in a variable embedding setting. In: ISAAC 1998. LNCS, vol. 1533, pp. 79–88. Springer (1998)

1998
[16]

In: GD 2018

Didimo, W., Liotta, G., Patrignani, M.: Bend-minimum orthogonal drawings in quadratic time. In: GD 2018. LNCS, vol. 11282, pp. 481–494. Springer (2018)

2018
[17]

Didimo, W., Liotta, G., Patrignani, M.: HV-planarity: Algorithms and complexity. J. Comput. Syst. Sci. 99, 72–90 (2019)

2019
[18]

Monographs in Com- puter Science, Springer (1999)

Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Com- puter Science, Springer (1999)

1999
[19]

Algorithmica 52(2), 267–292 (2008)

Dujmovi´ c, V., Fellows, M.R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. Algorithmica 52(2), 267–292 (2008)

2008
[20]

Dujmovi´ c, V., Fernau, H., Kaufmann, M.: Fixed parameter algorithms for one- sided crossing minimization revisited. J. Discrete Algorithms 6(2), 313–323 (2008) 14 E. Di Giacomo, G. Liotta, F. Montecchiani

2008
[21]

Algorithmica 40(1), 15–31 (2004)

Dujmovi´ c, V., Whitesides, S.: An eﬃcient ﬁxed parameter tractable algorithm for 1-sided crossing minimization. Algorithmica 40(1), 15–31 (2004)

2004
[22]

In: Handbook of Graph Drawing and Visualization, pp

Duncan, C.A., Goodrich, M.T.: Planar orthogonal and polyline drawing algo- rithms. In: Handbook of Graph Drawing and Visualization, pp. 223–246. Chapman and Hall/CRC (2013)

2013
[23]

In: LATIN 2014

Durocher, S., Felsner, S., Mehrabi, S., Mondal, D.: Drawing HV-restricted planar graphs. In: LATIN 2014. LNCS, vol. 8392, pp. 156–167. Springer (2014)

2014
[24]

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)

2001
[25]

Healy, P., Lynch, K.: Two ﬁxed-parameter tractable algorithms for test- ing upward planarity. Int. J. Found. Comput. Sci. 17(5), 1095–1114 (2006). https://doi.org/10.1142/S0129054106004285

2006 doi
[26]

Kloks, T.: Treewidth, Computations and Approximations, LNCS, vol. 842. Springer (1994)

1994
[27]

IEICE Transactions 88-D(1), 23–30 (2005)

Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. IEICE Transactions 88-D(1), 23–30 (2005)

2005
[28]

Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)

1986
[29]

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comp. 16(3), 421–444 (1987)

1987
[30]

Zhou, X., Nishizeki, T.: Orthogonal drawings of series-parallel graphs with mini- mum bends. SIAM J. Discrete Math. 22(4), 1570–1604 (2008) Orthogonal Planarity of Bounded Treewidth Graphs 15 Appendix A Additional Material for Section 3 Lemma 1 (*). Let G = (V,E ) be a planar ...

2008

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complex- ity of 1-planarity. J. Graph Algorithms Appl. 22(1), 23–49 (2018). https://doi.org/10.7155/jgaa.00457

doi:10.7155/jgaa.00457 2018

[2] [2]

Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page draw- ings of graphs with bounded treewidth. J. Graph Algorithms Appl. 22(4), 577–606 (2018). https://doi.org/10.7155/jgaa.00479

doi:10.7155/jgaa.00479 2018

[3] [3]

Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159–180 (1998)

work page 1998

[4] [4]

ACM Trans

Biedl, T.C., Lubiw, A., Petrick, M., Spriggs, M.J.: Morphing orthogonal planar graph drawings. ACM Trans. Algorithms 9(4), 29:1–29:24 (2013)

work page 2013

[5] [5]

Algorithmica 68(4), 859–885 (2014)

Bl¨ asius, T., Krug, M., Rutter, I., Wagner, D.: Orthogonal graph drawing with ﬂexibility constraints. Algorithmica 68(4), 859–885 (2014)

work page 2014

[6] [6]

Bl¨ asius, T., Lehmann, S., Rutter, I.: Orthogonal graph drawing with inﬂexible edges. Comput. Geom. 55, 26–40 (2016)

work page 2016

[7] [7]

Bodlaender, H.L.: A linear-time algorithm for ﬁnding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)

work page 1996

[8] [8]

In: IPEC 2013

Bodlaender, H.L., Bonsma, P.S., Lokshtanov, D.: The ﬁne details of fast dynamic programming over tree decompositions. In: IPEC 2013. LNCS, vol. 8246, pp. 41–53. Springer (2013)

work page 2013