arXiv:2606.25719v1 [cs.AI] 24 Jun 2026
Position Spaces and Graphs Rita-Nathalia Assaf ∗1 , Tom Davot†1 , Frédéric Lardeux‡1 , and Frédéric Saubion§1 1
Univ Angers, LERIA, SFR MATHSTIC, F-49000 Angers, France
Abstract In this paper, we introduce position graphs, a graph-based reasoning framework based on the formalization of position spaces. This framework utilizes two strict partial orders, representing horizontal and vertical alignment and precedence, to model the relative positions of discrete tokens. Unlike general qualitative spatial calculi, position graphs are constrained by a chain condition and compatibility requirements that focus on rows and columns. We provide a comprehensive theoretical analysis of this representation, beginning with a characterization of graph consistency. Conditions to ensure the consistency of position graphs are established. Furthermore, we investigate the computational complexity of structural pattern discovery, modeled as the induced subgraph isomorphism problem. We demonstrate that this problem remains NP-complete even within the restricted class of position graphs. While initially motivated by document processing, this work focuses on the underlying mathematical properties and algebraic consistency of position-based constraints, providing a formal logical layer that is independent of specific data extraction techniques.
1
Introduction
Reasoning about spatial organization is a fundamental problem in Artificial Intelligence when one seeks to infer structures from partial, symbolic information rather than from precise metric data. Such qualitative descriptions arise in domains ranging from document layout ∗
[email protected] [email protected] ‡ [email protected] § [email protected] †
1
analysis (Saout et al., 2024) (a motivating application for this work) to constraint-based modeling and spatial process calculi (Knight et al., 2012), and more broadly in qualitative spatial reasoning (Chen et al., 2015). Unlike approaches devoted to extracting spatial relations (Buck et al., 2022; Tian, 2024), we assume that qualitative positional constraints are already given, and our goal is to reason about their consistency, their logical consequences, and the occurrence of given structural patterns (e.g., find table structures in documents). Qualitative spatial reasoning provides expressive calculi for representing such knowledge. RCC8 (Randell et al., 1992; Cohn et al., 1997) is a canonical example, offering a logical language for topological relations with well-studied complexity properties (Renz and Nebel, 1999) and practical SAT-based reasoning techniques (Glorian et al., 2018). However, many layout-like tasks rely not on region topology but on simple alignment and precedence information, such as left-to-right or top-to-bottom relations between discrete tokens. This motivates the introduction of a lightweight qualitative framework capturing alignment constraints with precise mathematical semantics and a direct connection to constraint satisfaction problems. We introduce position spaces, based on a finite set of tokens with two alignment relations, horizontal and vertical, each modeled as a strict partial order. These relations encode one-dimensional precedence without committing to numerical coordinates. To reflect the intended semantics of rows and columns, we impose a local no-branching restriction: the successors (resp. predecessors) of a token along an alignment must form a chain. Furthermore, the two alignments must be compatible, in the sense that they admit a coherent two-dimensional interpretation. A position space satisfying these conditions is said to be consistent. Unlike dimension-2 posets or products of chains, our notion of a position space introduces two independent strict partial orders whose interactions are governed by new exclusivity and non-overlapping conditions, yielding a qualitatively new formal object. Moreover, we define a minimal set of algebraic constraints ensuring coherent two-dimensional alignment, with regard to a canonical interpretation. Position spaces admit a natural representation as labeled directed graphs, called position graphs, whose arcs encode horizontal or vertical precedence in the spirit of classical order graph-based representations. This enables two central reasoning tasks. First, we characterize consistency through forbidden patterns in mixed-label paths and provide a linear-time algorithm that constructs a valid row/column assignment whenever the space is consistent. Second, we study the discovery of patterns: given two position graphs, we ask whether the smaller appears as an induced, labelpreserving subgraph of the larger. We prove that induced subgraph
2
isomorphism remains NP-complete even within the restricted class of position graphs, establishing a hardness boundary that complements the tractability of consistency checking.
Contributions. The paper proposes the following contributions : • the formal definition of position spaces with no-branching and compatibility conditions capturing coherent row/column semantics, • a labeled graph representation and a characterization of consistency via forbidden mixed-label paths, • a linear-time row/column assignment algorithm that allows us to check the consistency of a position space, • an NP-completeness result for induced subgraph isomorphism on position graphs. Note that we do not aim to present a new layout engine/solver for practical cases, as in (Saout et al., 2023). In contrast, the present work focuses on the essential theoretical foundations—consistency proofs and algorithmic complexity—for such an application. In particular, the identification of NP-completeness for pattern matching in position graphs provides a necessary theoretical constraint for practitioners, justifying the move toward the heuristic-based approaches.
Organization. Section 2 introduces position spaces and position graphs. In Section 3, we study consistency from an algorithmic point of view. Section 4 formalizes pattern discovery and proves NP-completeness. Section 5 discusses related work in ordered structures, graph theory, qualitative reasoning and constraint-based modeling.
2
Position Space
We actually adopt a horizontal/vertical positioning point of view and hence, we rely on partial order relations to define the relative positioning of objects/items/tokens. An alignment relation defines how elements are aligned and in what order they are aligned to capture usual notions of row/column.
2.1
Position Space
Definition 1 (Alignment Relation, see Figure 1). Given a set of tokens T , an alignment relation < defined on T × T is a strict partial order such that ∀t, t′ , t′′ ∈ T , we have • (t < t′ ∧ t < t′′ ) ⇒ (t′ < t′′ ∨ t′′ < t′ ), and
3
• (t′ < t ∧ t′′ < t) ⇒ (t′ < t′′ ∨ t′′ < t′ ).
t′
t′
t′′
⇒
t
t′′
t t′
t′′
⇒
t′′
or
t′
t
t
t
t
t′ t′′
or
t′′ t′
Figure 1: Illustration of conditions satisfied by an alignment relation. A chain of an alignment relation < on a set of tokens T is a totally ordered subset of T , i.e. a sequence of tokens (t1 , . . . , tk ) such that for all i ∈ [k − 1], ti < ti+1 , where [k − 1] is the integer interval [1, · · · , k − 1]. The conditions introduced in Definition 1 prevent the presence of inconsistent alignments from our point of view, meaning alignments that correspond to an incongruent division of the same row/column. Note that we consider a strict partial order relation. Although < is formally a strict partial order, our intended semantics for an alignment is one-dimensional: horizontal (resp. vertical) alignment represents left-to-right (resp. top-to-bottom) ordering within a single row (resp. column). We get the following property immediately. Property 1 (Chain Condition). For every token t ∈ T and an alignment relation < on T , both the set of successors {u ∈ T | t < u} and the set of predecessors {u ∈ T | u < t} are chains. Definition 2 (Position Space). A position space is a triplet (T , <h , <v ) such that <h (horizontal alignment) and <v (vertical alignment) are two alignment relations defined on T . A position space defines the organization of tokens according to their vertical and horizontal alignments. We assume that every element of T must have a relative positioning with respect to at least one other element (either vertical or horizontal). Note that this latter assumption is not mandatory in our framework. If one wishes to relax this constraint, it suffices to consider reflexive relations, which does not fundamentally change the rest of the discussion.
4
2.2
Consistency of a Position Space
As mentioned in the introduction, we aim to ensure that our alignment relations represent horizontal and vertical positions that are coherent with their canonical interpretation. Hence, in this section, we precisely define a compatibility property to ensure the consistency of a position space. Definition 3 (v-chain). Let Π = (T, <h , <v ) be a position space. A sequence of tokens (t1 , . . . , tk ) is called a v-chain if the following two conditions hold: 1. for every i ∈ {1, . . . , k − 1}, at least one of the following holds: ti <h ti+1 ,
ti+1 <h ti ,
ti <v ti+1 ;
2. there exists at least one index i ∈ {0, . . . , k − 1} such that ti <v ti+1 . An h-chain is defined symmetrically. Intuitively, in a v-chain, consecutive tokens are either related by <h , regardless of the direction, or ordered by <v , with at least one pair ordered by <v . An h-chain is defined symmetrically. Definition 4 (Compatibility of alignment relations). Given a position space P = (T , <h , <v ), <h and <v are said to be compatible if and only if for any pair of tokens t, t′ ∈ T such that t <h t′ (resp. t <v t′ ), there is no v-chain (resp. h-chain) between t and t′ . Observe that this condition ensures that two tokens can be ordered by at most one alignment relation. Definition 5. A position space (T , <h , <v ) whose relations are compatible is said to be consistent. Figure 2 illustrates two basic cases of inconsistent position spaces. Note that grid or lattice graphs may share some similarities with our approach; however, such graphs are generally regular and consider integer-coordinate points as vertices, with edges representing pairs of vertices that share one coordinate. Here, we aim for a more specific and declarative representation based on alignments.
2.3
Position Graph
Graphs constitute a natural representation of partial ordering relations (e.g., Hasse diagrams (Hasse, 1952) that also avoid transitivity direct representation). Moreover, as pointed out in the introduction, one of our aims is to identify particular patterns within position spaces, and graphs are a natural framework for modeling this problem.
5
t4 t1
t2
t5
t1 t2
t3
t4
t3
t6
Figure 2: Illustration of inconsistent position spaces. Vertical alignments are depicted with a blue arc while horizontal alignments are depicted with a green arc. In all cases, consistency is violated because t1 <v t3 and there is a h-chain between t1 and t3 containing a horizontal alignment relation. Definition 6 (Position Graph). Given a position space Π = (T , <h , <v ), the induced position graph GPΠ is defined as a labeled directed graph (T , A, E) where A ⊆ T × T and E : T × T → {h, v} such that: • ∀t, t′ ∈ T , t <h t′ ⇔ (t, t′ ) ∈ A ∧ E(t, t′ ) = h, and • ∀t, t′ ∈ T , t <v t′ ⇔ (t, t′ ) ∈ A ∧ E(t, t′ ) = v. Example 1. Let T = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. We define our position space by setting: 1 <h 2, 2 <h 3, 3 <h 4, 5 <h 6, 6 <h 7, 8 <h 9, 9 <h 10, 1 <v 5, 5 <v 8, 2 <v 6, 6 <v 9, 9 <v 11, 3 <v 7, 7 <v 10. For Example 1, we obtain the graph shown in Figure 3. In Figure 3, we omit the labels of the arcs because those labeled ’h’ will be drawn in green and horizontally and those labeled ’v’ in blue and vertically. Definition 7 (Consistent Position Graph). A position graph is said to be consistent if and only if its corresponding position space is consistent. A v-cycle is a sequence of tokens (t1 , . . . , tk = t1 ) such that there is an arc with label v between ti and ti+1 for some i ∈ [k − 1] and for all i ∈ [k − 1], either (ti , ti+1 ) ∈ A or (ti+1 , ti ) ∈ A with E(ti+1 , ti ) = h. A h-cycle is defined symmetrically. Definition 4 yields the following characterization. Property 2 (Characterization of a Consistent Position Graph). A position graph GPΠ = (T , A, E) is consistent if and only if it does not contain a v-cycle or an h-cycle. Proof. Let (T , <h , <v ) be a consistent position space and let GPΠ be its corresponding position graph. Let t and t′ be two tokens such that t <h t′ (resp. t <v t′ ). If there is a v-chain (resp. h-chain) (t1 = t, . . . , tk = t′ ) between t and t′ , then there is a v-cycle (resp.
6
t1
t4
t7
t2
t5
t8
t3
t6
t9
t10
t11 Figure 3: Position graph GP . h-cycle) (t1 = t, . . . , tk = t′ , t) in GPΠ since there is an arc labelled h (resp. v) between t and t′ . Moreover, if there is a v-cycle (resp. h-cycle) (t1 = t, . . . , tk−1 = t′ , tk = t) in GPΠ , then there is a v-chain (resp. h-chain) (t1 = t, . . . , tk−1 = t′ ) in Π. Hence, (T , <h , <v ) does not contain a v-chain (resp. h-chain) if and only if GPΠ does not contain a v-cycle (resp. h-cycle). In the next section, we study the consistency of the position space from an algorithmic perspective. We propose an algorithm that checks if a position space is consistent by trying to assign row and column indices to each element of the position space.
7
3 Rows/Columns Embedding of Position Spaces We now address the Rows/Columns (R/C) embedding problem, which consists of assigning concrete positions to tokens. Intuitively, given a consistent position space Π = (T , <h , <v ), we want to introduce notions of rows and columns such that the alignment relations <h and <v are respected: if t <h t′ , then t and t′ should be on the same row with t′ to the right of t and if t <v t′ , then t and t′ should be on the same column with t′ below t. We first define rows and columns with regard to the notion of chains previously defined. Definition 8 (Rows and Columns). Given a position space Π = (T , <h , <v ), a row (resp. a column) is a maximal chain contained in <h (resp. <v ). RΠ and CΠ are the sets of rows and columns of Π, respectively. Observe that a token necessarily belongs to a column and a row: a token not comparable in <h (resp. <v ) forms a singleton row (resp. column). Moreover, a token cannot belong to two distinct rows (resp. columns), as this would either contradict the transitivity of <h (resp. <v ) or the maximality of the chains. Hence, the following property follows. Property 3. Given a consistent position space Π = (T , <h , <v ), the set of rows (resp. columns) RΠ (resp. CΠ ) forms a partition of T . Given a consistent position graph GPΠ = (T , A, E), we define the graph of columns GΠ C of GPΠ obtained by contracting each column into a single vertex. Formally, ′ ′ ′ ′ GΠ C = (CΠ , {(C, C ) | ∃t ∈ C, t ∈ C , (t, t ) ∈ A}).
The graph of rows of GΠ R of GPΠ is defined symmetrically. Note that the rows and columns as in Definition 8 can be computed in linear time in the input size, i.e., O(|T |+|A|) by computing connected components in the subgraphs induced by h-arcs and v-arcs, respectively. Definition 9 (R/C embedding). Given a position space Π = (T , <h , <v ), a R/C embedding of Π is a mapping T → |RΠ | × |CΠ | that assigns to each token t ∈ T a row number xt and a column number yt such that: • xt = xt′ if and only if t <h t′ or t′ <h t, • if t <h t′ , then yt < yt′ , • yt = yt′ if and only if t <v t′ or t′ <v t, and • if t <v t′ , then xt < xt′ .
8
Property 4. If a position space Π is inconsistent, then it does not admit an R/C embedding. Proof. Assume, toward a contradiction, that Π = (T, <h , <v ) is inconsistent and admits an R/C embedding. Since Π is inconsistent, by Definition 4 there are two possible cases. We treat one of them, the other being symmetric. Suppose there exist two tokens t, t′ ∈ T such that t <h t′ and there exists a v-chain (t0 , . . . , tk ) with t0 = t and tk = t′ . Since t <h t′ , we must have xt = xt′ . Now consider any consecutive pair (ti , ti+1 ) in the v-chain. By definition of a v-chain, one of the following holds: • ti <h ti+1 , in which case xti = xti+1 ; • ti+1 <h ti , in which case again xti = xti+1 ; • ti <v ti+1 , in which case xti < xti+1 . Therefore, for every i ∈ {0, . . . , k − 1}, we have xti ≤ xti+1 . Moreover, since (t0 , . . . , tk ) is a v-chain, there exists at least one index i such that ti <v ti+1 , and hence xti < xti+1 . We get xt = xt0 < xtk = xt′ , which contradicts xt = xt′ . The case where t <v t′ and there exists an h-chain from t to t′ is symmetric, using the column numbers yt instead of the row numbers xt . Hence, Π does not admit an R/C embedding. Lemma 1. A position graph GPΠ = (T , A, E) is inconsistent if and only if either its graph of columns or its graph of rows contains a directed cycle. Proof. Suppose without loss of generality that there is a cycle (C1 , . . . , Ck = Π C1 ) in GΠ C . Then, by construction of GC , for all i ∈ [k − 1], there is out in in a token ti ∈ Ci and a token ti+1 ∈ Ci+1 such that E(tout i , ti+1 ) = h. in out out in Moreover, for each ∈ [k], we have that E(ti , ti ) = v or E(ti , ti ) = in out in in out v. Thus, the sequence (tout 1 , t2 , t2 , t3 , . . . , t1 , t1 ) is an h-cycle and so, GPΠ is inconsistent. Now suppose that GPΠ is inconsistent. And suppose without loss of generality that GPΠ contains an h-cycle (t1 , . . . , tk = t1 ). For w = (C1 , . . . , Ck ) be the sequence of columns such that ti ∈ Ci for all i ∈ [k]. Clearly, if Ci ̸= Ci+1 , then E(ti , ti+1 ) = v by construction of GΠ C , and Π so (Ci , Ci+1 ) is an arc in GΠ C . Hence, w is a closed walk in GC and Π thus, GC contains a cycle. It follows that if GPΠ is consistent, then we can order the vertices Π GΠ C and GR and use that order to produce an R/C embedding for Π.
9
Algorithm 1: R/C embedding of a position space Input: Position Graph GPΠ = (T , A, E) Output: A R/C embedding for Π or Inconsistent Π 1 if GΠ C or GR contain a directed cycle then 2 return Inconsistent 3 end 4 TR = {R1 , . . . , R|RΠ | } ← topological ordering of RΠ 5 foreach Ri ∈ TR do 6 foreach t ∈ Ri do 7 xt ← i 8 end 9 end 10 TC = {C1 , . . . , C|CΠ | } ← topological ordering of CΠ 11 foreach Ci ∈ TC do 12 foreach t ∈ Ci do 13 yt ← i 14 end 15 end
Theorem 1. If GPΠ is consistent, then Algorithm 1 produces an R/C embedding for Π in O(|T | + |A|) time. Proof. First, by Property 3, each token belongs to a column and a row and thus, each token t receives values xt and yt on lines 7 and 13. Further, we need to show that the mapping is an R/C embedding. Let t and t′ be any pair of tokens such that t <h t′ . We want to show that yt < yt′ and xt = xt′ . By definition, t and t′ belong to the same row and since the algorithm gives the same value xt to all tokens of a row (line 7), we have xt = xt′ . Suppose for contradiction that there are two tokens t and t′ such that t <h t′ and yt′ ≤ yt . Let C and C ′ be the columns containing t and t′ , respectively. Since t <h t′ , there is an arc between C and C ′ . If C = C ′ , then there is a loop in GΠ C , which is a contradiction. So, C ̸= C ′ and we necessarily have that yt ̸= yt′ since the algorithm selects one column at a time. Since yt′ < yt , the column C ′ has been selected before C by the algorithm. But then, since there is an arc between C and C ′ , it contradicts GΠ C being acyclic. Hence, we cannot have yt′ ≤ yt . The case where t <v t′ is symmetric. Finally, since the algorithm assigns a different value yt (resp. xt ) to two tokens if they do not belong to the same column (resp. row), it follows that the produced mapping is an R/C embedding. Π Regarding the complexity, the construction of GΠ C and GR can be
10
Π done in O(|T | + |A|). Detecting a cycle in GΠ C or GR can be done in O(|T | + |A|) using a Breadth-First Search. Computing a topological ordering can be done in O(|T | + |A|) using Kahn’s algorithm. We obtain an overall complexity of O(|T | + |A|).
We may now fully characterize consistent position spaces with regard to the induced notions of rows and columns. Corollary 1. There is a R/C embedding for Π if and only if Π is consistent. At this step, the notion of position space has been precisely defined from its initial description by means of ordering relations to its graph representation. We are now able to use it for a specific task, already mentioned: the discovery of a particular token pattern.
4
Subgraph Isomorphism
Position graphs provide a natural representation of alignment relations and, as such, can be used to detect structural configurations of interest. As discussed earlier, our primary motivation is the identification of specific arrangements of tokens that may correspond to meaningful document structures, such as tables in document analysis (Saout et al., 2023). Despite the additional structural constraints imposed by position graphs, we show in the next section that the problem of searching for a pattern in such graphs remains NP-complete. To formalize this task, let G and H be two position graphs. We are interested in determining whether the pattern graph H occurs in the target graph G. The graph H is itself a position graph, typically smaller than G, whose vertices should be understood as placeholders to be matched with actual tokens of G. For the complexity proofs that follow, it is convenient to use standard graph-theoretic notation, since vertices and arcs will encode elements related to Boolean formulas rather than document tokens directly. Accordingly, for a graph X, we denote by V (X) its vertex set and by A(X) its arc set. Two directed graphs G and H are said to be isomorphic if there exists a bijection g : V (H) → V (G) such that, for all u, v ∈ V (H), (u, v) ∈ A(H) ⇐⇒ (g(u), g(v)) ∈ A(G). In the specific case of position graphs, the isomorphism must additionally preserve arc labels. More precisely, if G and H are position graphs with labeling functions EG : A(G) → {h, v} and EH : A(H) → {h, v}, then an isomorphism g must satisfy EH (u, v) = EG (g(u), g(v)) for every arc (u, v) ∈ A(H). In other words, both adjacency and the type of alignment relation (horizontal or vertical) must be preserved. In summary, such a bijection g allows us to identify a subgraph in G that is isomorphic to H.
11
Finding a specific pattern (the graph H) in a given position space (the target graph G), corresponds then to the Induced Subgraph Isomorphism problem formulated as : Induced Subgraph Isomorphism Input : two graphs G and H. Question : does G contain an induced subgraph isomorphic to H Remember that a general subgraph of G may omit some edges between chosen vertices. In contrast, an induced subgraph cannot omit them (it preserves both adjacency and non-adjacency within A(G)). We model pattern discovery as induced subgraph isomorphism. In position graphs, arcs represent precedence constraints (horizontal/vertical alignments), and the absence of an arc is itself informative, expressing non-comparability/no direct precedence within the extracted constraint network. Consequently, a correct occurrence of a structural template must preserve not only the required relations but also the non-relations among the matched tokens. This is exactly captured by induced subgraph isomorphism, which preserves adjacency and nonadjacency, unlike general subgraph isomorphism that may ignore extra host edges among selected vertices. In the following, when constructing an isomorphism g, we say that we identify a path (v1 , . . . , vi ) of H to a path (u1 , . . . , ui ) of G by setting g(vj ) = uj for all j ≤ i. A transitive vertical path (resp. transitive horizontal path) (v1 , . . . , vi ) is a transitively closed directed path in which every arc is labeled v (resp. h). In the remainder of this section, we show that Induced Subgraph Isomorphism is NP-complete when G and H are consistent position graphs. Let us recall that 3-SAT is the decision problem of determining whether a CNF Boolean formula, with each clause containing exactly three literals (variables or negations), is satisfiable. 3-SAT is known to be NP-complete (Cook, 1971). Construction 1 (Target Graph, see Figure 4). Let φ be a 3-SAT formula with Boolean variables set {x1 , . . . , xn } and clauses set {Q1 , . . . , Qm }. We construct a target position graph G with vertex set V (G) = {o, qi , qi∗ , qip , uj , fji , tij , fj∗ , t∗j , ℓij , ℓ̄ij | p ∈ [3], i ∈ [m], j ∈ [n]}. • Introduce a transitive horizontal path A = (o, q1 , . . . , qm ) and a transitive vertical path B = (o, u1 , . . . , un ). • For each clause Qi , – introduce the transitive horizontal path (qi∗ , qi1 , qi2 , qi3 ),
12
– introduce the vertical arc (qi , qi∗ ), and – for each k ≤ 3, let xj be the k th variable occurring in Qi , introduce the vertical arc (qik , ℓij ) if xj appears positively in Qi and the vertical arc (qik , ℓ̄ij ) otherwise. • For each variable xj , – introduce a transitive horizontal path (uj , fj∗ , t∗j ), and – introduce two transitive vertical paths Fj = (fj∗ , fj1 , . . . , fjm ) and Tj = (t∗j , t1j , . . . , tm j ), • For each clause Qi and each variable xj , introduce the two horizontal arcs (tij , ℓ̄ij ) and (fji , ℓij ). Property 5. The graph G defined by Construction 1 is a consistent position graph Proof. First, we show that the graph of rows GΠ R does not contain a cycle. Consider the following vertex partition P0 ∪ · · · ∪ Pn of G: • P0 = {o, qi , qi∗ , qip | i ∈ [m], p ∈ [3]}, • ∀j ∈ [n], Pj = {uj , fji , tij , fj∗ , t∗j , ℓij , ℓ̄ij | i ∈ [m]} Observe that by construction, each row of G is contained in a single part. Moreover, no part Pk contains a cycle of GΠ R . Now, we show that for any vertical arc (u, v) such that u ∈ Pi , v ∈ Pj and Pi ̸= Pj , we have i < j. For the arc (o, u1 ), we have o ∈ P0 and u1 ∈ P1 . For any arc (ui , ui+1 ), we have ui ∈ Pi and ui+1 ∈ Pi+1 . For any arc (qip , ℓij ), we have qip ∈ P0 and ℓij ∈ Pj , with j ≥ 1. Finally, for any arc (qip , ℓ̄ij ), we have qip ∈ P0 and ℓ̄ij ∈ Pj , with j ≥ 1. Hence, it follows that the graph of rows does not contain a cycle. Further, we show in a similar manner that the graph of columns GΠ C does not contain a cycle. Consider the following vertex partition P0 ∪ · · · ∪ Pn of G: • P0 = {o, uj , fji , tij , fj∗ , t∗j | i ∈ [m], j ∈ [m]}, • ∀i ∈ [m], Pi = {qi , qi∗ , qij , ℓij , ℓ̄ij | p ∈ [3], j ∈ [n]}. Observe that by construction, each column of G is contained in a single part. Moreover, no part Pk contains a cycle of GΠ C . Now, we show that for any horizontal arc (u, v) such that u ∈ Pi , v ∈ Pj and Pi ̸= Pj , we have i < j. For the arc (o, q1 ), we have o ∈ P0 and q1 ∈ P1 . For any arc (qi , qi+1 ), we have qi ∈ Pi and qi+1 ∈ Pi+1 . For any arc (tij , ℓ̄ij ), we have tij ∈ P0 and ℓ̄ij ∈ Pi , with i ≥ 1. Finally, for any arc (fji , ℓij ), we have fji ∈ P0 and ℓij ∈ Pi , with i ≥ 1. Hence, it follows that the graph of columns does not contain a cycle. Hence, By Lemma 1, G is consistent.
13
q1
o
q11
q1∗ f1∗
u1
q12
q13
q3 q21
q2∗
t11
ℓ̄11
t21
ℓ̄21
q32
q33
ℓ̄31
t∗2 t12
ℓ̄12
t22
ℓ̄22
t32
f21
ℓ̄32
ℓ12
f22
ℓ22
f23
ℓ32 f3∗
t∗3 t13
ℓ̄13
t23
ℓ̄23
t33
ℓ̄33
ℓ13
f32 f33
q31
ℓ31 f2∗
f31
q3∗
ℓ21
f13
u3
q23
ℓ11
f12
u2
q22
t∗1
t31
f11
q2
ℓ23 ℓ33
Figure 4: Example of graphs produced by Construction 1 with input formula φ = (¬x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x2 ∨ x3 ) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3 ). For greater clarity, the transitive arcs have not been depicted.
14
k1
w
k2 s1
k1∗ y1∗
v1
k3 s2
k2∗ s′1
y11
z11
y12
z12
y13
k3∗ s′2
s3 s′3
z13 y2∗
v2 y21
z21
y22
z22
y23
z23 y3∗
v3 y31
z31
y32
z32
y33
z33
Figure 5: Example of a graph produced by Construction 2 with input formula φ = (¬x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x2 ∨ x3 ) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3 ). Let us now define the graph that corresponds to the pattern. Construction 2 (Pattern, see Figure 5). Let φ be a 3-SAT formula with n variables and m clauses. We construct a position graph H with vertex set V (H) = {w, ki , ki∗ , si , s′i , vj , yj∗ , yji , zji | i ∈ [m], j ∈ [n]}, as follows. • Introduce a transitive horizontal path A′ = (w, k1 , . . . , km ) and a transitive vertical path B ′ = (w, v1 , . . . , vn ). • For each clause Qi , introduce the horizontal arc (ki∗ , si ) and the two vertical arcs (ki , ki∗ ) and (si , s′i ). • For each variable xj , introduce the vertical arc (vj , yj∗ ) and a transitive horizontal path Xj = (yj∗ , yj1 , . . . , yjm ).
15
Property 6. The graph H defined by Construction 2 is a consistent position graph The proof is similar to that of Property 5 and is even simpler. Lemma 2. Let φ be a 3-SAT formula and let G and H be two position graphs produced by Constructions 1 and 2, respectively. If G contains a subgraph isomorphic to H, then there is an isomorphism f such that: 1. A′ is identified with A, B ′ is identified with B, and 2. for each variable xj ∈ φ, Xj is identified with either Tj or Fj . Proof. 1. By construction, A is the only transitive horizontal path containing m+1 vertices, so A′ is necessarily identified with A. It follows that w is identified with o and B ′ is identified with B. 2. By the previous item, for each variable xj ∈ φ, vj is identified with uj . Since uj has two horizontal neighbors fj∗ and t∗j , yj∗ is identified with one of them. It follows that Xj is identified with either Tj or Fj .
Theorem 2. Induced Subgraph Isomorphism is NP-complete even when restricted to position graphs. Proof. The problem belongs to NP, since given an injective mapping g : V (H) → V (G), one can verify in polynomial time that it defines a label-preserving induced subgraph isomorphism by checking adjacency, non-adjacency, and arc labels. Let φ be a 3-SAT formula and let G and H be two position graphs produced by Constructions 1 and 2, respectively. We show that φ is satisfiable if and only if G contains an induced subgraph isomorphic to H. • Let β be a satisfying assignment for φ. We construct the following isomorphism g between H and a subgraph of G. First, we identify A′ with A and B ′ with B. For each variable xj ∈ φ, if xj is assigned to true, we identify Xj with Tj and for each i ≤ m, we identify zji with ℓ̄ij . If xj is assigned to false, we identify Xj with Fj and for each i ≤ m, we identify zji with ℓij . For each clause Qi , we identify ki∗ with qi∗ . It remains to assign g(si ) and g(s′i ) for each clause Qi . For every clause Qi , there exists a variable xj ∈ Qi such that its assignment in β satisfies Qi . Suppose that xj is the tth variable occurring in Qi . If xj occurs positively (resp. negatively) in Qi , then by previous mapping, ℓij are not associated yet with any node (resp. ℓ̄ij are not associated yet with any node), and we can set g(si ) = qit and g(s′i ) = ℓij
16
(resp. g(s′i ) = ℓ̄ij ). We have constructed an injective mapping g such that for all pairs of vertices u, v, (u, v) ∈ A(H) if and only if (g(u), g(v)) ∈ A(G) and such that for all arc (u, v) ∈ A(H), (u, v) and (g(u), g(v)) have the same label. It remains to observe that the image of g induces in G exactly the arcs prescribed by H. Indeed, by construction, every selected vertex lies on one of the designated clause or variable gadgets, and the only arcs between selected vertices are precisely those used to realize the paths and attachments of H. In particular, no additional arc of G connects two vertices in the image of g unless the corresponding vertices are adjacent in H. Therefore, g is an induced, label-preserving subgraph isomorphism from H into G. Hence, G contains an induced subgraph isomorphic to H. • Let g be an isomorphism respecting Lemma 2. We construct an assignment for φ as follows: for each variable xi ∈ φ, we assign xi to true if Xi is identified with Ti and we assign xi to false otherwise. Toward a contradiction, suppose there is a clause Qi that is not satisfied. Suppose that g(s′i ) = ℓij . By construction, the variable xj occurs positively in Qi . Since Qi is not satisfied, xj is assigned to false and so, Xj is identified with Fj . In particular, we have g(yji ) = fji . But then, since ℓij is the only horizontal neighbor of fji , we have necessarily g(zji ) = ℓij . Thus, |g −1 (ℓij )| ≥ 2 which contradicts g being an isomorphism. If g(s′i ) = ℓ̄ij , then we also obtain a contradiction by symmetry. Therefore, all clauses are satisfied by β, which concludes the proof.
5 Existing Approaches: Relationships and Limitations This section aims to review several types of works that can be connected to our main representation concern. We argue that the position space is a distinct construct that cannot be directly replaced by existing methods.
5.1 Ordered structures, transitive orientations, and multidimensional patterns Our representation is related to several works connecting order theory and graph structure. Partially ordered sets (posets) admit graphical encodings via comparability graphs, where edges reflect comparabilities in the underlying order; equivalently, these are precisely the graphs
17
that admit a transitive orientation (Golumbic, 1977, 1980). This perspective has been extensively developed, including recognition and orientation algorithms for transitively orientable graphs (Golumbic, 1977, 1980). Position graphs may thus be viewed as a constrained, edgelabeled analogue of such structures: their horizontal and vertical labels restrict which transitive orientations correspond to valid spatial interpretations and impose compatibility conditions beyond transitivity alone. A complementary point of view is developed in the theory of poset dimension, defined as the minimum number of linear extensions whose intersection yields the poset. Dimension theory connects order structure to geometric realizability in Rd under the product order and provides criteria for when an ordering admits a low-dimensional coordinate representation (Trotter, 1992). Although related in spirit to two-dimensional order embeddings, our framework differs by explicitly separating two alignment relations and enforcing cross-relation consistency constraints not captured by standard dimension arguments. More precisely, a poset has dimension 2 when its order relation can be expressed as the intersection of two linear extensions (Trotter, 1992). In such settings, the two linear orders represent different views of the same underlying hierarchy, and a pair (x, y) is comparable only if both extensions agree on their ordering. In contrast, a position space defines two independent strict partial orders, <h and <v , each with a distinct spatial interpretation (horizontal versus vertical). Moreover, the exclusivity condition of Definition 4 prevents a pair of tokens from being comparable in both relations. As a consequence, position spaces do not correspond to dimension-2 posets: instead of intersecting two total orders to define a single order relation, they maintain two disjoint precedence structures that cannot be merged into a unified poset. Classical grid or geometric embeddings of posets (e.g., using dominance orders, rectangle representations, or boxicity embeddings) aim to represent a single partial order in two-dimensional space by assigning each element coordinates or regions whose geometric relations preserve the order. Although consistent position spaces also admit a twodimensional layout through their row/column assignment, this embedding does not represent a global poset order. Instead, it preserves <h and <v independently, and the exclusivity condition prevents the existence of a single coordinate-wise order capturing both. Thus, despite similarities, position spaces are structurally distinct from classical grid embeddings: they encode two orthogonal alignment relations rather than a two-dimensional realization of a single poset. Let us also remark that the direct product of two linear orders defines the classical 2-dimensional grid poset: (a, b) ≤ (c, d) if and only if a ≤ c and b ≤ d. This coordinate-wise comparison requires that
18
ordered pairs satisfy both dimensional constraints. Position spaces behave differently: comparability is defined separately by one alignment relation, either horizontal or vertical, but never both. Hence, position spaces do not directly form a subclass of product orders. Finally, pattern detection in ordered structures also relates to permutation patterns and the avoidance/containment paradigm, where containment is defined through preservation of relative order in subsequences (Bóna, 2004; Marcus and Tardos, 2004). Classical permutation patterns operate over a single total order; in contrast, our setting involves two interacting order relations together with labeled edges, connecting it more closely to multidimensional generalizations of containment than to the one-dimensional theory of permutation patterns.
5.2
Subgraph and Induced Subgraph Isomorphism
Many works investigate graph pattern matching—particularly subgraph and induced-subgraph isomorphism, as the task of identifying occurrences of a smaller pattern inside a larger structure, a problem that becomes especially intricate for labeled graphs and directed acyclic targets. Classical and modern practical approaches emphasize filter-andsearch pipelines and constraint-programming–inspired pruning strategies, especially for large graphs with small pattern queries (McCreesh et al., 2018). Recent developments introduce new heuristics and structural refinements tailored for labeled or directed settings, as illustrated by (Asiler et al., 2022), which provides an efficient subgraph-isomorphism framework for large graph databases, or FiPE (Lu et al., 2025), a subgraph-matching algorithm that eliminates redundant computations by defining fine-grained equivalence relations over vertex pairs and multi-vertex patterns. The Glasgow Subgraph Solver further exemplifies state-of-the-art constraint-guided backtracking with support for both induced and non-induced variants and parallel execution (McCreesh et al., 2020). LAD2025 (Solnon, 2026) also provides a modern constraint-based solver for the subgraph-isomorphism problem, strengthening domain filtering and constraint propagation to achieve competitive performance on a broad range of benchmark instances. Since position graphs in our setting are directed and acyclic, the problem naturally falls within labeled pattern matching on DAG-like structures, where the induced requirement—preserving both adjacency and non-adjacency—typically increases difficulty relative to non-induced matching; empirical studies show that induced and non-induced instances can behave quite differently in practice, even when both formulations remain NP-complete (McCreesh et al., 2018). Induced subgraph isomorphism itself is a classical NP-complete problem (Garey and Johnson, 1979). Despite this worst-case hardness, decades of practical work—including recent large-scale experiments—demonstrate that
19
many real-world instances are solvable using modern pruning and search strategies, although hard families persist and motivate the exploitation of domain-specific structure, particularly in specialized graphical representations such as DAG-like position graphs.
5.3
Qualitative Spatial Reasoning
Qualitative Spatial Reasoning (QSR) (Chen et al., 2015) allows reasoning about spatial relationships without relying on precise numerical coordinates, unlike quantitative approaches. QSR focuses on symbolic and relational descriptions of space, which are particularly useful in domains where exact measurements are unavailable, unnecessary, or computationally expensive. One of the most known frameworks in QSR is RCC8 (Region Connection Calculus) (Randell et al., 1992), which defines eight mutually exclusive and jointly exhaustive base relations: Disconnected (DC), Externally Connected (EC), Partially Overlapping (PO), Equal (EQ), Tangential Proper Part (TPP), Non-Tangential Proper Part (NTPP), and their inverses (TPPi, NTPPi). These relations capture fundamental aspects of spatial configuration without relying on precise numerical coordinates, making RCC8 particularly suitable for applications (Cohn et al., 1997) in geographic information systems, spatial databases, and AI reasoning tasks . These rules focus on topological relationships between regions (e.g., disconnected, overlapping, and contained). RCC8 abstracts metric details but still assumes continuous spatial regions. The relations provide a logical calculus system for reasoning about connectivity and containment. Our approach focuses on the relative positioning of discrete tokens using horizontal and vertical alignment relations. The spatial organization is represented by strict partial orders rather than topological predicates. We also emphasize rows and columns and their compatibility, enabling declarative modeling of layout-like structures. Hence, QSR is more region-centric, whereas the proposed approach is tokencentric. However, RCC8 does not encode direction or order (e.g., “A is left of B” or “C is above D”). To recover the horizontal (h) and vertical (v) edge semantics of a Position Graph, we should combine RCC8 with a directional calculus such as the Cardinal Direction Calculus (CDC) (Frank, 1992) or Rectangle Algebra (RA) (Mukerjee and Joe, 1990).Example 2 illustrates these relationships between position graphs and description logics. Example 2 (Mapping Position Graphs to Qualitative Constraints). Assume a Position Graph (T , A, E). We may construct a qualitative spatial reasoning constraint network with one region variable per token. For each token t ∈ T , create a region variable Rt . We can use RCC8
20
to forbid overlaps where the graph prohibits them, and to allow/force contacts where alignment suggests adjacency. If, in the intended layout, two different columns in the same row must not overlap, set: ∀ t, t′ in same row but different columns:
(Rt , Rt′ ) ∈ {DC, EC}.
Choose DC if gaps are mandatory; choose EC if touching is permitted (adjacent cells). Analogous reasoning is performed for rows: ∀ t, t′ in same column but different rows:
(Rt , Rt′ ) ∈ {DC, EC}.
If the model needs cells or rows/columns as container regions, we may use TPP/NTPP to encode that a token lies properly inside its row/column region: (Rt , Rrow(t) ) ∈ {T P P, N T P P },
(Rt , Rcol(t) ) ∈ {T P P, N T P P }.
TPP vs NTPP distinguishes whether the token touches the boundary of the container. To capture order (left–right for h, above–below for v), add CDC (or RA) constraints. For every horizontal edge E(t, t′ ) = h: CDC(Rt , Rt′ ) ∈ {W, W−NW, W−SW}, i.e., t lies west of t′ . (You can pick a single cardinal relation W if you want strict west-of.). For every vertical edge E(t, t′ ) = v: CDC(Rt , Rt′ ) ∈ {N, N−NE, N−NW}, i.e., t lies north of t′ . (Likewise, choose N for strict north-of ) Mixing RCC8 with CDC is, of course, computationally expensive, as shown in (Liu et al., 2009). Note that (Röhrig, 1994) proposed a theory for qualitative spatial reasoning by expressing spatial concepts through simple order relations on low-dimensional structures.
6
Conclusion
In this work, we introduced position spaces and their graph representation, position graphs, as a lightweight qualitative framework for reasoning about the relative organization of discrete tokens using two strict partial orders capturing horizontal and vertical precedence. By imposing a chain (no-branching) condition on successors and predecessors and a compatibility requirement that forbids mixed horizontal/vertical chains between tokens already ordered in one direction, we
21
formalized when such positional information admits a coherent twodimensional interpretation in terms of rows and columns. We then provided a structural characterization of consistency for position graphs and showed how consistency can be checked constructively. Building on this characterization, we designed an R/C embedding algorithm that assigns row and column indices to tokens whenever the position space is consistent, and proved that it runs in linear time in the size of the graph. Beyond consistency, we studied structural pattern discovery as a graph-matching problem and modeled it as label-preserving induced subgraph isomorphism between position graphs. We established a strong hardness boundary by proving that induced subgraph isomorphism remains NP-complete even when restricted to consistent position graphs, despite the substantial structural constraints imposed by the position space axioms. This separation clarifies which reasoning tasks can be solved reliably at scale and which will generally require heuristics or specialized solvers in practical applications such as document layout analysis. As future work, an important direction is to identify maximal tractable fragments of the induced matching problem within position graphs, enabling efficient discovery of useful pattern families while retaining the formal benefits of the proposed representation.
References Saout, T., Lardeux, F., Saubion, F.: An overview of data extraction from invoices. IEEE Access 12, 19872–19886 (2024) https://doi.org/10.1109/ACCESS.2024.3360528 Knight, S., Palamidessi, C., Panangaden, P., Valencia, F.D.: Spatial and epistemic modalities in constraint-based process calculi. In: Koutny, M., Ulidowski, I. (eds.) CONCUR 2012 – Concurrency Theory – 23rd International Conference, CONCUR 2012, Newcastle upon Tyne, UK, September 4–7, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7454, pp. 317–332. Springer, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32940-1 23 Chen, J., Cohn, A.G., Liu, D., Wang, S., Ouyang, J., Yu, Q.: A survey of qualitative spatial representations. Knowl. Eng. Rev. 30(1), 106– 136 (2015) https://doi.org/10.1017/S0269888913000350 Buck, A.R., Anderson, D.T., Keller, J.M., Luke, R.H., Scott, G.: A comparison of relative position descriptors for 3d objects. In: 2022 IEEE International Conference on Fuzzy Sys-
22
tems (FUZZ-IEEE), pp. 1–10 (2022). https://doi.org/10.1109/FUZZIEEE55066.2022.9882693 Tian, Z.: A new representation method of the relative position between objects in the image based on the histogram of position sensing forces. Scientific Reports 14, 764 (2024) https://doi.org/10.1038/s41598-024-51396-x Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning. KR’92, pp. 165–176. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1992) Cohn, A.G., Bennett, B., Gooday, J., Gotts, N.M.: Qualitative spatial representation and reasoning with the region connection calculus. GeoInformatica 1(3), 275–316 (1997) https://doi.org/10.1023/A:1009712514511 Renz, J., Nebel, B.: On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artif. Intell. 108(1-2), 69–123 (1999) https://doi.org/10.1016/S00043702(99)00002-8 Glorian, G., Lagniez, J.-M., Montmirail, V., Sioutis, M.: An incremental SAT-based approach to reason efficiently on qualitative constraint networks. In: Hooker, J.N. (ed.) Principles and Practice of Constraint Programming – 24th International Conference, CP 2018, Lille, France, August 27–31, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11008, pp. 160–178. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98334-9 11 Saout, T., Lardeux, F., Saubion, F.: A two-stage approach for tables extraction in invoices. In: 35th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2023, Atlanta, GA, USA, November 6-8, 2023, pp. 10–15. IEEE, Los Alamitos, CA (2023) Hasse, H.: Über die Klassenzahl Abelscher Zahlkörper. De Gruyter, Berlin, Boston (1952). https://doi.org/10.1515/9783112471388 Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. STOC ’71, pp. 151–158. Association for Computing Machinery, New York, NY, USA (1971). https://doi.org/10.1145/800157.805047 Golumbic, M.C.: The complexity of comparability graph recognition and coloring. Computing 18(3), 199–208 (1977)
23
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). Classic reference on comparability graphs and transitive orientations Trotter, W.T.: Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore (1992) Bóna, M.: Combinatorics of Permutations. Chapman & Hall/CRC, Boca Raton (2004) Marcus, A., Tardos, G.: Excluded permutation matrices and the stanley–wilf conjecture. Journal of Combinatorial Theory, Series A 107(1), 153–160 (2004) McCreesh, C., Prosser, P., Solnon, C., Trimble, J.: When subgraph isomorphism is really hard, and why this matters for graph databases. Journal of Artificial Intelligence Research 61, 723–759 (2018) Asiler, M., Yazici, A., George, R.: Hygraph: a subgraph isomorphism algorithm for efficiently querying big graph databases. J. Big Data 9(1), 40 (2022) https://doi.org/10.1186/S40537-022-00589-0 Lu, Y., Zhang, Z., Zheng, W., Zou, L.: Accelerating subgraph matching through fine-grained and powerful equivalences. Proc. VLDB Endow. 18(11), 3896–3909 (2025) https://doi.org/10.14778/3749646.3749662 McCreesh, C., Prosser, P., Trimble, J.: The glasgow subgraph solver: Using constraint programming to tackle hard subgraph isomorphism problem variants. In: Gadducci, F., Kehrer, T. (eds.) Graph Transformation – 13th International Conference, ICGT 2020, Bergen, Norway, June 25–26, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12150, pp. 316–324. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51372-6-19 Solnon, C.: Lad2025, A constraint-based solver for the subgraph isomorphism problem. Artif. Intell. 352, 104474 (2026) https://doi.org/10.1016/J.ARTINT.2025.104474 Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979) Frank, A.U.: Qualitative spatial reasoning about distances and directions in geographic space. J. Vis. Lang. Comput. 3(4), 343–371 (1992) https://doi.org/10.1016/1045-926X(92)90007-9
24
Mukerjee, A., Joe, G.: A qualitative model for space. In: Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90), pp. 721–727. AAAI Press, Menlo Park, CA (1990). https://aaai.org/papers/00721-aaai90-108-a-qualitativemodel-for-space/ Liu, W., Li, S., Renz, J.: Combining RCC-8 with qualitative direction calculi: Algorithms and complexity. In: Boutilier, C. (ed.) IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pp. 854–859 (2009). http://ijcai.org/Proceedings/09/Papers/146.pdf Röhrig, R.: A theory for qualitative spatial reasoning based on order relations. In: Hayes-Roth, B., Korf, R.E. (eds.) Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31 - August 4, 1994, Volume 2, pp. 1418– 1423. AAAI Press / The MIT Press, Menlo Park, CA (1994). http://www.aaai.org/Library/AAAI/1994/aaai94-218.php
25