pith. sign in

arxiv: 1907.01630 · v1 · pith:UL2Q2Q5Tnew · submitted 2019-07-02 · 💻 cs.DS · cs.CG

Computing k-Modal Embeddings of Planar Digraphs

Juan Jose Besa , Giordano Da Lozzo , Michael T. Goodrich This is my paper

Pith reviewed 2026-05-25 10:24 UTC · model grok-4.3

classification 💻 cs.DS cs.CG
keywords k-modal embeddingplanar digraphgraph embeddingorientation constraintcombinatorial embeddingclustered network
0
0 comments X

The pith

A planar digraph admits a k-modal embedding when its edges at each vertex can be grouped into at most k consecutive runs of the same orientation.

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

The paper defines a k-modal embedding of a planar digraph as one in which every vertex is incident to at most k pairs of consecutive edges whose orientations are opposite. It introduces the k-Modality decision problem that asks whether such an embedding exists for a given planar digraph and even integer k. The authors state that this problem sits at the core of multiple constrained embedding tasks for planar digraphs and flat clustered networks. A reader would care because an efficient solution to k-Modality would supply a combinatorial handle on orientation-aware layout problems that arise in network visualization.

Core claim

The k-Modality problem asks for the existence of a k-modal embedding of a planar digraph, where an embedding is k-modal if every vertex is incident to at most k pairs of consecutive edges with opposite orientations, i.e., the incoming and outgoing edges at each vertex are grouped by the embedding into at most k sets of consecutive edges with the same orientation. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks.

What carries the argument

k-modal embedding: a plane embedding of a digraph in which the alternation between incoming and outgoing edges around each vertex is bounded by k.

If this is right

  • An algorithm for k-Modality immediately yields algorithms for the constrained embedding problems that reduce to it.
  • The same combinatorial condition applies uniformly to both planar digraphs and flat clustered networks.
  • The evenness requirement on k is necessary for the grouping of same-orientation edges to be feasible around a vertex.

Where Pith is reading between the lines

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

  • If the reduction from application constraints to k-Modality is tight, then hardness results for k-Modality would transfer directly to those applications.
  • The problem may admit a linear-time solution via planarity-testing techniques augmented with local rotation constraints at each vertex.

Load-bearing premise

The combinatorial definition of k-modal embedding directly encodes the orientation constraints that appear in the embedding applications the paper references.

What would settle it

A concrete planar digraph together with an application-specific embedding constraint that cannot be expressed as a bound of k on consecutive opposite-orientation pairs at any vertex.

Figures

Figures reproduced from arXiv: 1907.01630 by Giordano Da Lozzo, Juan Jose Besa, Michael T. Goodrich.

Figure 1
Figure 1. Figure 1: (a) A planar L-drawing, which determines a 4-modal embedding. (b) A planar NodeTrix [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) Illustrations for the duality between the canonical digraph and the canonical c-graph. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (left) A 4-modal embedding of a simply-connected planar digraph [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration for the proof of Lemma 5. The parity of t and t 0 is the same at uµ and different at vµ; in particular, even if a new alternation is introduced between the pair (e, e0 ) at vµ, the different parity guarantees that the modality at vµ does not increase from E to E 0 . t ∈ S such that t  t 0 . Also, S reduces S 0 if S  S 0 and S ⊆ S 0 . Finally, S is a gist of S 0 , if S is succinct and reduces… view at source ↗
read the original abstract

Given a planar digraph $G$ and a positive even integer $k$, an embedding of $G$ in the plane is k-modal, if every vertex of $G$ is incident to at most $k$ pairs of consecutive edges with opposite orientations, i.e., the incoming and the outgoing edges at each vertex are grouped by the embedding into at most k sets of consecutive edges with the same orientation. In this paper, we study the $k$-Modality problem, which asks for the existence of a $k$-modal embedding of a planar digraph. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks.

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.

Referee Report

1 major / 0 minor

Summary. The paper defines a k-modal embedding of a planar digraph G (for even positive integer k) as one in which every vertex has at most k pairs of consecutive edges with opposite orientations, i.e., incoming and outgoing edges are grouped into at most k consecutive same-orientation blocks. It studies the k-Modality decision problem of whether such an embedding exists and asserts that this combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks.

Significance. If the centrality claim holds via explicit reductions and the manuscript supplies a correct polynomial-time algorithm or characterization for k-Modality, the work would contribute to the theory of orientation-constrained planar embeddings. The current manuscript, however, provides no such reductions or algorithmic details in support of the core claim.

major comments (1)
  1. [Abstract] Abstract: The claim that k-Modality 'is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks' is unsupported; no reduction, derivation, or example is given showing that the combinatorial condition (at most k opposite-orientation pairs per vertex) arises directly from the cited target problems. This is load-bearing for the paper's motivation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive comment regarding the abstract. We address the concern point-by-point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The claim that k-Modality 'is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks' is unsupported; no reduction, derivation, or example is given showing that the combinatorial condition (at most k opposite-orientation pairs per vertex) arises directly from the cited target problems. This is load-bearing for the paper's motivation.

    Authors: We agree that the abstract statement is motivational and lacks explicit support (reductions, derivations, or concrete examples) within the manuscript. The claim was intended to contextualize the problem based on connections observed in the broader literature on orientation-constrained embeddings, but the current version does not derive or illustrate those connections. We will revise the abstract to remove the unsupported phrasing and replace it with a more precise statement focused on the combinatorial problem itself. If the page limit permits, we will also add a brief motivating paragraph in the introduction that provides at least one concrete example of how the k-modal condition arises from a related embedding question. revision: yes

Circularity Check

0 steps flagged

No circularity detected; no derivation chain or reductions present

full rationale

The provided abstract defines the k-modal embedding combinatorially and asserts without derivation that the k-Modality problem 'is at the very core of a variety of constrained embedding questions.' No equations, reductions, predictions, or self-citations are shown that could reduce to inputs by construction. The centrality claim is an unsupported assertion rather than a derived result, so none of the enumerated circularity patterns apply. This matches the reader's assessment that no derivation or reduction is shown.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no equations, parameters, or proofs; ledger is empty by necessity.

pith-pipeline@v0.9.0 · 5647 in / 938 out tokens · 25840 ms · 2026-05-25T10:24:41.318258+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Angelini, G

    P. Angelini, G. Da Lozzo, M. D. Bartolomeo, V. D. Donato, M. Patrignani, V. Roselli, and I. G. Tollis. Algorithms and bounds for L-drawings of directed graphs. Int. J. of Foundations of Computer Science , 29(04):461–480, 2018

    work page 2018

  2. [2]

    Angelini, G

    P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, and I. Rutter. Beyond level planarity. In Y. Hu and M. N¨ ollenburg, editors,GD ’16, volume 9801 of LNCS, pages 482–495. Springer, 2016

    work page 2016

  3. [3]

    Angelini, G

    P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, M. Patrignani, and I. Rutter. Intersection- link representations of graphs. J. Graph Algorithms Appl. , 21(4):731–755, 2017

    work page 2017

  4. [4]

    Angelini, G

    P. Angelini, G. Da Lozzo, G. Di Battista, F. Frati, and V. Roselli. The importance of being proper: (in clustered-level planarity and T-level planarity). Theor. Comput. Sci. , 571:1–9, 2015

    work page 2015

  5. [5]

    Angelini, P

    P. Angelini, P. Eades, S. Hong, K. Klein, S. G. Kobourov, G. Liotta, A. Navarra, and A. Tappini. Turning cliques into paths to achieve planarity. In T. C. Biedl and A. Kerren, editors, GD 2018, volume 11282 of LNCS, pages 67–74. Springer, 2018

    work page 2018

  6. [6]

    Angelini, G

    P. Angelini, G. D. Lozzo, G. D. Battista, V. D. Donato, P. Kindermann, G. Rote, and I. Rutter. Windrose planarity: Embedding graphs with direction-constrained edges. ACM Trans. Algorithms, 14(4):54:1–54:24, Sept. 2018

    work page 2018

  7. [7]

    Bachmaier, F

    C. Bachmaier, F. Brandenburg, and M. Forster. Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl. , 9(1):53–97, 2005. 12

    work page 2005

  8. [8]

    Bertolazzi, G

    P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings of triconnected digraphs. Algorithmica, 12(6):476–497, 1994

    work page 1994

  9. [9]

    Binucci, W

    C. Binucci, W. Didimo, and F. Giordano. Maximum upward planar subgraphs of embedded planar digraphs. Comput. Geom., 41(3):230–246, 2008

    work page 2008

  10. [10]

    Binucci, W

    C. Binucci, W. Didimo, and M. Patrignani. Upward and quasi-upward planarity testing of embedded mixed graphs. Theor. Comput. Sci. , 526:75–89, 2014

    work page 2014

  11. [11]

    K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. , 13(3):335–379, 1976

    work page 1976

  12. [12]

    Br¨ uckner and I

    G. Br¨ uckner and I. Rutter. Partial and constrained level planarity. In P. N. Klein, editor, SODA ’17, pages 2000–2011. SIAM, 2017

    work page 2000

  13. [13]

    Chaplick, M

    S. Chaplick, M. Chimani, S. Cornelsen, G. Da Lozzo, M. N¨ ollenburg, M. Patrignani, I. G. Tollis, and A. Wolff. Planar L-drawings of directed graphs. In F. Frati and K. Ma, editors, GD ’17, volume 10692 of LNCS, pages 465–478. Springer, 2017

    work page 2017

  14. [14]

    Da Lozzo, G

    G. Da Lozzo, G. Di Battista, F. Frati, and M. Patrignani. Computing nodetrix representations of clustered graphs. J. Graph Algorithms Appl. , 22(2):139–176, 2018

    work page 2018

  15. [15]

    Di Battista and E

    G. Di Battista and E. Nardelli. Hierarchies and planarity theory. IEEE Trans. Systems, Man, and Cybernetics , 18(6):1035–1046, 1988

    work page 1988

  16. [16]

    Di Battista and R

    G. Di Battista and R. Tamassia. On-line graph algorithms with spqr-trees. In M. Paterson, editor, ICALP ’90, volume 443 of LNCS, pages 598–611. Springer, 1990

    work page 1990

  17. [17]

    Garg and R

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

    work page 2001

  18. [18]

    E. D. Giacomo, G. Liotta, M. Patrignani, and A. Tappini. Nodetrix planarity testing with small clusters. In F. Frati and K. Ma, editors, GD ’17 , volume 10692 of LNCS, pages 479–491. Springer, 2017

    work page 2017

  19. [19]

    Henry, J

    N. Henry, J. Fekete, and M. J. McGuffin. Nodetrix: a hybrid visualization of social networks. IEEE Trans. Vis. Comput. Graph. , 13(6):1302–1309, 2007

    work page 2007

  20. [20]

    J. E. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549–568, 1974

    work page 1974

  21. [21]

    J¨ unger, S

    M. J¨ unger, S. Leipert, and P. Mutzel. Level planarity testing in linear time. In S. Whitesides, editor, GD ’98, volume 1547 of LNCS, pages 224–237. Springer, 1998

    work page 1998

  22. [22]

    Klemz and G

    B. Klemz and G. Rote. Ordered level planarity, geodesic planarity and bi-monotonicity. In F. Frati and K. Ma, editors, GD ’17, volume 10692 of LNCS, pages 440–453. Springer, 2017

    work page 2017

  23. [23]

    J. Lu, Y. Zhang, J. Xu, G. Xiao, and Q. A. Liang. Data visualization of web service with parallel coordinates and nodetrix. In IEEE International Conference on Services Computing, SCC 2014, Anchorage, AK, USA, June 27 - July 2, 2014 , pages 766–773. IEEE Computer Society, 2014

    work page 2014

  24. [24]

    B. M. E. Moret. Planar nae3sat is in p. SIGACT News, 19(2):51–54, June 1988

    work page 1988

  25. [25]

    Porschen, B

    S. Porschen, B. Randerath, and E. Speckenmeyer. Linear time algorithms for some not-all- equal satisfiability problems. In E. Giunchiglia and A. Tacchella, editors, SAT ’03, volume 2919 of LNCS, pages 172–187. Springer, 2003. 13

    work page 2003

  26. [26]

    X. Yang, L. Shi, M. Daianu, H. Tong, Q. Liu, and P. M. Thompson. Blockwise human brain network visual comparison using nodetrix representation. IEEE Trans. Vis. Comput. Graph., 23(1):181–190, 2017. 14

    work page 2017