Oriented interval graphs, a recent generalization of interval graphs introduced by Gutowski et al. [GD 2022], are intersection graphs of intervals, each of which is oriented either left or right. Such a representation defines a mixed intersection graph: overlapping intervals with the same orientation define a (directed) arc; nested intervals (irrespective of the orientations of the intervals) and overlapping intervals of opposite orientations define an (undirected) edge. An oriented interval representation of a mixed graph G can be described combinatorially by the combination of (i) an orientation φ : V(G) → {-1,1} of all intervals, (ii) a clique ordering σ, and (iii) a set E_cont ⊆ E(G) of containment edges, which are represented by nested intervals. The non-trivial dependencies between these three ingredients make the recognition of oriented interval graphs a challenging problem. In this paper, we take steps towards a general recognition algorithm by studying how orientation, clique ordering, and containment edges influence and restrict each other. We characterize the orientations that are consistent with a given set of containment edges as well as the clique orderings that are consistent with a given orientation. Based on these characterizations, we give linear-time algorithms for two constrained versions of the recognition problem where, in addition to the mixed input graph G, either the set of containment edges E_cont or the orientation φ is prescribed. This improves a quadratic-time algorithm of Gutowski et al. for the case that all vertices have the same orientation; an assumption that determines both the orientation and the containment edges. In particular, this also solves the recognition problem for oriented proper (or unit) interval graphs.

The visibility graph of a set S ⊆ ℝ² is the graph whose vertices are the points of S, with two points x,y connected by an edge if and only if they see each other in S, that is, if the segment xy is contained in S. The edge density of this graph is known as the Beer index of S. Previously, it has been shown that a simply connected set S ⊆ ℝ² of unit Lebesgue measure with Beer index β > 0 contains a convex subset of measure Ω(β); in particular, for visibility graphs of simply connected sets, a positive edge density β > 0 implies the existence of a clique containing an Ω(β)-fraction of all vertices. The simple-connectivity assumption cannot be omitted, as there are non-simply-connected sets with Beer index 1 and no convex subset of positive measure. Nevertheless, in this paper, we extend the above result to non-simply-connected sets, by showing that a visibility graph with large edge density contains a triangle with large convex hull. More precisely, we show that a set S ⊆ ℝ² of unit Lebesgue measure with Beer index β > 0 contains three pairwise visible points whose convex hull has measure Ω(β⁹). If in addition S is an open domain with K holes, then S contains three pairwise visible points with convex hull of measure Ω(β/K) as well as a convex subset of measure Ω(β/K²).

We introduce a new complexity measure for cocomparability graphs of posets or in other words, intersection graphs of piecewise linear functions, the bend number. We prove that cocomparability graphs of bounded bend number are not too plentiful and give two hierarchies of classes of cocomparability graphs, depending on whether the piecewise linear functions are restricted to slopes of ±1 (diagonal case) or not (general case). These hierarchies give a gradation between permutation graphs and cocomparability graphs.

Abstract In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs—the simultaneous version of arguably one of the most well-studied graph classes—is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more ‘rigid’ and therefore have less freedom in their representation. We show they can be recognized in time $$\mathcal {O}(|V|\cdot |E|)$$ O ( | V | · | E | ) for any number of simultaneous graphs in the sunflower case where $$G=(V,E)$$ G = ( V , E ) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.

We consider three simple quadratic time algorithms for the problem Level Planarity and give a level-planar instance that they either falsely report as negative or for which they output a drawing that is not level planar.

Abstract The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph $$H \subseteq G$$ H ⊆ G and a representation $$\mathcal R'$$ R ′ of H. The question is whether G admits a representation $$\mathcal R$$ R whose restriction to H is $$\mathcal R'$$ R ′ . We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams. We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in $$O((n + m) \alpha (n + m))$$ O ( ( n + m ) α ( n + m ) ) time, thereby improving over an $$O(n^3)$$ O ( n 3 ) -time algorithm by Chaplick et al. (J Graph Theory 91(4), 365–394, 2019). The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.

Abstract A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coincide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial representation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs.

A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coincide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial representation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs.

Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time $O((n+m)α(n+m))$ where $n$ is the number of vertices, $m$ is the number of edges and $α$ is the inverse Ackermann function. Our algorithm is based on the minimal split decomposition [Cunnigham, 1982] and uses the state-of-art circle graph recognition algorithm [Gioan, Paul, Tedder, Corneil, 2014] in the same running time. It improves the running time $O(nm)$ of the previous algorithm [Hsu, 1995] based on a similar approach.

In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs - the simultaneous version of arguably one of the most well-studied graph classes - is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more "rigid" and therefore have less freedom in their representation. We show they can be recognized in time O(|V|*|E|) for any number of simultaneous graphs in the sunflower case where G=(V,E) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.

Power Factor Correction (PFC) converters belong to the variable structure piecewise linear systems due to the switching action. Their complex behaviour is intensively studied. Present paper represents a stability analysis method using the socalled auxiliary state vector to determine the Jacobian matrix of the Poincare Map Function (PMF) to calculate the critical angle where oscillations developes in the inductor current. The effect caused by the Zero-Order Hold, the digital computation delays and the nonideal circuit elements are taken into consideration. Furthermore by adding a stabilizing signal the stable range can be extended. The parameters of the stabilizing signal is also determined by the auxiliary state vector. The theoretic results are verified by simulation and the experiment results.

One possible implementation form of Pulse Width Modulation is the naturally sampled one (NS-PWM). Its favourable properties are that no distortion or delayed response are introduced by it. The paper compares three different realizations of NS-PWM techniques by simulations and experimental measurements when the carrier over reference frequency ratio mf is small number as in inverters supplying ultrahigh speed induction motor (USIM). The three NS-PWM techniques are the Sinusoidal, Sinusoidal and third-harmonic reference injection and the Space Vector Modulation. The paper verifies both by simulation and laboratory results that the three techniques generate DC voltage component in the output voltage of the inverter contrary to many previous publications. In addition subharmonic currents and fluxes with considerable amplitudes are produced as well due to the small mf and very low subharmonic frequency even though the subharmonic voltage component is very small.