Search

Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs—a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a richer class of graphs. In particular, mixed unit interval graphs may contain a claw as an induced subgraph, as opposed to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs and demonstrate the advantages of this generalized model by providing a subexponential-time algorithm for solving the MaxCut problem on mixed unit interval graphs. In addition, we derive a polynomial-time algorithm for certain subclasses of mixed unit interval graphs. We point out a substantial mistake in the proof of the polynomiality of the MaxCut problem on unit interval graphs by Boyacı et al. (Inf Process Lett 121:29–33, 2017. https://doi.org/10.1016/j.ipl.2017.01.007). Hence, the time complexity of this problem on unit interval graphs remains open. We further provide a better algorithmic upper-bound on the clique-width of mixed unit interval graphs. [ABSTRACT FROM AUTHOR]

We describe the missing class of the hierarchy of mixed unit interval graphs. This class is generated by the intersection graphs of families of unit intervals that are allowed to be closed, open, and left-closed-right-open. (By symmetry, considering closed, open, and right-closed-left-open unit intervals generates the same class.) We show that this class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as quadratic-time algorithms that recognize graphs from this class and produce a corresponding interval representation if one exists. We also show that the algorithm from Shuchat et al. [8] directly extends to provide a quadratic-time algorithm to recognize the class of mixed unit interval graphs. [ABSTRACT FROM AUTHOR]

Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker (J Comput Syst Sci 13:335-379, 1976) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension. The input of this problem consists of a graph G with a partial representation $${{{\mathcal {R}}}}'$$ fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation $${{{\mathcal {R}}}}$$ of the entire graph G extending $${{{\mathcal {R}}}}'$$ . We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15:835-855, 1965) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees. [ABSTRACT FROM AUTHOR]

We propose an Eulerian thermodynamically compatible model for ideal plasticity of crystalline solids treated as a material flow through an adjustable crystal lattice space. The model is based on the additive splitting of the velocity gradient into the crystal lattice part and the plastic part. The approach extends a Gibbs-potential-based formulation developed in Rajagopal and Srinivasa (2011) for obtaining the response functions for elasto-visco-plastic crystals. The framework makes constitutive assumptions for two scalar functions: the Gibbs potential and the rate of dissipation. The constitutive equations relating the stress to kinematical quantities is then determined using the condition that the rate of dissipation is maximal providing that the relevant constraints are met. The proposed model is applied to three-dimensional micropillar compression, and its features, both on the level of modelling and computer simulations, are discussed and compared to relevant studies. [ABSTRACT FROM AUTHOR]

Deformation bands are interpreted as a spontaneously formed microstructure caused by anisotropy induced by the slip nature of plastic deformation. The gradient terms in the proposed constitutive equations have been derived by averaging the assembly of discrete dislocations. The rigid-plastic model points to the main constituents which control the fragmentation mechanism: anisotropy of the hardening matrix, anisotropic resistance of the boundaries to slip, and the bowing (Orowan) stress. For symmetric double slip compression, the model provides an explanation of the observed band orientation and band width, and of the significant change in structural morphology seen as the band reorientation occurs at large strains. The predictions are in favorable agreement with available observations. [ABSTRACT FROM AUTHOR]

We study the problem of drawing simultaneously embedded graphs with few bends. We show that for any simultaneous embedding with fixed edges (SEFE) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (SGE) for a non-trivial class of graphs. [ABSTRACT FROM AUTHOR]

A covering projection from a graph G onto a graph H is a mapping of the vertices of G onto the vertices of H such that, for every vertex v of G , the neighborhood of v is mapped bijectively onto the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetric graphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved. We investigate the computational complexity of the problem of deciding the existence of a covering projection from an input graph G to a fixed target graph H . Among other partial results this problem has been shown NP-hard for simple regular graphs H of valency greater than 2, and a full characterization of computational complexity has been shown for target multigraphs with 2 vertices. We extend the previously known results to the ternary case, i.e., we give a full characterization of the computational complexity in the case of multigraphs with 3 vertices. We show that even in this case a P/NP-completeness dichotomy holds. [ABSTRACT FROM AUTHOR]

Chordal graphs are intersection graphs of subtrees of a tree T . We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T ′ and some pre-drawn subtrees of T ′ . It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e., keeps the pre-drawn subtrees unchanged). We consider four modifications of T ′ leading to vastly different problems: (i) T = T ′ , (ii) T is a subdivision of T ′ , (iii) T is a supergraph of T ′ , and (iv) T ′ is a topological minor of T . In some cases, it is interesting to consider the complexity even when just T ′ is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components of the input graph G and the size of the tree T ′ . We describe an interesting relation with integer partition problems. The problem 3-Partition is used for all NP -completeness reductions. When the space in T ′ is limited, partial representation extension of proper interval graphs is “equivalent” to the BinPacking  problem. [ABSTRACT FROM AUTHOR]

In this paper, we consider the firefighter problem on a graph G = ( V , E ) that is either finite or infinite. Suppose that a fire breaks out at a given vertex v ∈ V . In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible (if G is finite) or to stop the fire from spreading (for an infinite case). The surviving rate ρ ( G ) of a finite graph G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a vertex of G that is selected uniformly random. For a finite square grid P n □ P n , we show that 5 / 8 + o ( 1 ) ≤ ρ ( P n □ P n ) ≤ 67 243 / 105 300 + o ( 1 ) (leaving the gap smaller than 0.0136) and conjecture that the surviving rate is asymptotic to 5/8. We define the surviving rate for infinite graphs and prove it to be 1 / 4 for the infinite square grid, even for more than one (but finitely many) initial fires. For the infinite hexagonal grid we provide a winning strategy if two additional vertices can be protected at any point of the process, and we conjecture that the firefighter has no strategy to stop the fire without additional help. We also show how the speed of the spreading fire can be reduced by a constant multiplicative factor. For triangular grid, we show that two firefighters can slow down the fire in the same sense, which is relevant to the conjecture that two firefighters cannot contain the fire on the triangular grid, and also corrects a previous result of Fogarty (2003). [ABSTRACT FROM AUTHOR]

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H-free graph. Polynomial-time algorithms are known for H having at most three vertices or isomorphic to P4. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP-complete, thus solving an open problem [Kratochvíl, Nešetřil and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K1, 2-free graph by ten forbidden-induced subgraphs, each having five vertices. We also give the forbidden-induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees. [ABSTRACT FROM AUTHOR]

The proposed model is inspired by Brown’s suggestion that the saturation stress in cycling is controlled by the stress required to separate two screw dislocations of opposite signs, which are just on the point of mutual annihilation by cross-slip. Cross-slip is treated as the deterministic, stress-activated process governed by the line tension, the applied stress and the interaction force between dislocations. The extension of the dislocation cores is neglected. The saturation stress and the critical cross-slip annihilation distance predicted simultaneously by the model agree with the available experimental data. [ABSTRACT FROM AUTHOR]

Abstract: Cross-slip is treated as a deterministic, mechanically activated process governed by the applied stress, by the interaction force between approaching screw dislocations of the opposite sign and by the line tension related to the persistent slip band channel width. The dislocations are modeled as moving polygons. In the evaluation of the critical cross-slip annihilation distance and the saturation stress in cycling, we accept two assumptions inspired by Brown [Brown L. Philos Mag A 2002;82:1691]: (i) the critical parameter associated with cross-slip is the spreading of the dislocation loop on the cross-slip plane, not the critical formation of a constriction in an extended screw dislocation core. (ii) The saturation stress in cycling is controlled by the stress required to separate two screw dislocations of opposite signs which are just on the point of mutual annihilation by cross-slip. The proposed model predicts the critical annihilation distance and the cyclic saturation stress in agreement with the available experimental data for Cu, Ni and Ag single crystals. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the -span of a graph is the minimum possible span of its -labelings. We show how to compute the -span of a connected graph in time . Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time for claw-free graphs, and in time for graphs having a dominating set of size . [Copyright &y& Elsevier]

Abstract: A - -labeling of a graph is a mapping from its vertex set into a set of integers such that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. The main result of the paper is an algorithm finding an optimal -labeling of a graph (i.e. an -labeling in which the largest label is the least possible) in time and polynomial space. Then we adapt our method to obtain a faster algorithm for - -labeling, where is a small positive constant. Moreover, a new interesting extremal graph theoretic problem is defined and solved. [Copyright &y& Elsevier]

Abstract: A partially embedded graph (or Peg) is a triple , where G is a graph, H is a subgraph of G, and is a planar embedding of H. We say that a Peg is planar if the graph G has a planar embedding that extends the embedding . We introduce a containment relation of Pegs analogous to graph minor containment, and characterize the minimal non-planar Pegs with respect to this relation. We show that all the minimal non-planar Pegs except for finitely many belong to a single easily recognizable and explicitly described infinite family. We also describe a more complicated containment relation which only has a finite number of minimal non-planar Pegs. Furthermore, by extending an existing planarity test for Pegs, we obtain a polynomial-time algorithm which, for a given Peg, either produces a planar embedding or identifies an obstruction. [Copyright &y& Elsevier]

Abstract: A graph is a segment graph if its vertices can be mapped to line segments in the plane such that two vertices are adjacent if and only if their corresponding line segments intersect. Kratochvíl and Kuběna asked the question of whether the complements of planar graphs, called co-planar graphs, are segment graphs. We show here that the complements of all partial 2-trees are segment graphs. [Copyright &y& Elsevier]

Abstract: Given two sets of non-negative integers, a set of vertices of a graph is -dominating if for every vertex , and for every . This concept, introduced by Telle in 1990’s, generalizes and unifies several variants of graph domination studied separately before. We study the parameterized complexity of -domination in this general setting. Among other results, we show that the existence of a -dominating set of size (and at most ) are W[1]-complete problems (when parameterized by ) for any pair of finite sets and . We further present results on dual parameterization by , and results on certain infinite sets (in particular for being the sets of even and odd integers). [Copyright &y& Elsevier]

A straight-line drawing δ of a planar graph G need not be plane but can be made so by untangling it, that is, by moving some of the vertices of G. Let shift( G, δ) denote the minimum number of vertices that need to be moved to untangle δ. We show that shift( G, δ) is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. Further we define fix( G, δ)= n−shift( G, δ) to be the maximum number of vertices of a planar n-vertex graph G that can be fixed when untangling δ. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log\log n}$ vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing δ G of G with $\ensuremath {\mathrm {fix}}(G,\delta_{G})\leq \sqrt{n-2}+1$ and an n-vertex outerplanar graph H and a drawing δ H of H with $\ensuremath {\mathrm {fix}}(H,\delta_{H})\leq2\sqrt{n-1}+1$ . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs. [ABSTRACT FROM AUTHOR]

Abstract: The proposed crystal plasticity model outlines a possible mechanism of a material response under severe plastic deformation as observed in high-pressure torsion experiments. A simplified version of the model based on an assumption of uniform deformation of plane-strain double slip reveals rotations of slip systems caused by the imposed shear strain. An axial compression and a shear stress of twist govern this process. The accompanied continuous reconstruction of the deformation substructure is probably one of the main reasons for the observed strengthening. Local variations in the crystal lattice orientation are responsible for the microstructure fragmentation. [Copyright &y& Elsevier]

Abstract: By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths. [Copyright &y& Elsevier]

Abstract: A mixed hypergraph is a triple where is its vertex set and and are families of subsets of , called -edges and -edges, respectively. For a proper coloring, we require that each -edge contains two vertices with the same color and each -edge contains two vertices with different colors. The feasible set of a mixed hypergraph is the set of all ''s for which there exists a proper coloring using exactly colors. A hypergraph is a hypertree if there exists a tree such that the edges of the hypergraph induce connected subgraphs of the tree. We prove that feasible sets of mixed hypertrees are gap-free, i.e., intervals of integers, and we show that this is not true for precolored mixed hypertrees. The problem to decide whether a mixed hypertree can be colored by colors is NP-complete in general; we investigate complexity of various restrictions of this problem and we characterize their complexity in most of the cases. [Copyright &y& Elsevier]

Abstract: We introduce a new notion of Systems of Distant Representatives of families of subsets of a metric space. We are in particular interested in the computational complexity of deciding the existence of such systems, for different distance parameters and for various metric spaces. The problem contains as a subproblem the well known polynomial time solvable problem of Systems of Distinct Representatives (for discrete metric and distance parameter 1). We prove several NP-hardness results, e.g., for discrete metric and distance parameter 2, or for Euclidean metric spaces. We also show a direct connection to practically motivated and previously studied problems such as scheduling, distance constrained graph labeling, map labeling, disjoint representatives of hypergraphs and independent sets in graphs. Finally, we mention our original motivation for studying distant representatives which comes from the distance constrained graph labeling and our complexity results imply a significant difference in the computational complexity of -labeling of trees for and . [Copyright &y& Elsevier]

Abstract: Branchwidth is a graph invariant closely related to treewidth, but exhibiting remarkable distinctions. E.g., branchwidth is known to be computable in polynomial time for planar graphs. Our results concern the computational complexity of determining the branchwidth of graphs in several classes. We give an algorithm computing the branchwidth of interval graphs in time . This method generalizes to permutation graphs and, more generally, to trapezoid graphs. In contrast, we show that computing branchwidth is NP-complete for splitgraphs and for bipartite graphs. [Copyright &y& Elsevier]

A variational formulation of the incrementally linear rigid-plastic approximation to crystal plasticity is set up. It is shown that the subgrain formation is a consequence of a tendency to minimize the sum of the incremental dissipated energy and the incremental energy that is related to the increase of flow stress. A physically motivated nonlocal formulation of the variational problem leads to a finite size of the subgrains formed. A crystal deformed by symmetric double slip is considered as an example. [Copyright &y& Elsevier]

A mixed hypergraph H is a triple (V,C,D) where V is its vertex set and C and D are families of subsets of V (called C-edges and D-edges). A vertex coloring of H is proper if each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The feasible set of H is the set of all k''s such that there exists a proper coloring using exactly k colors. The feasible set is gap-free if it is an interval of integers.A graph is a strong/weak cactus if all its cycles are vertex/edge-disjoint. A hypergraph is spanned by a graph (with the same vertex set) if the edges of the hypergraph induce connected subgraphs. A strong/weak hypercactus is spanned by a strong/weak cactus. We prove that the feasible set of any mixed strong hypercactus is gap-free. We find infinitely many mixed weak hypercacti such that the feasible set of any of them contains a gap. For each connected non-planar graph G≠K5, we find a mixed hypergraph spanned by G whose feasible set contains a gap. [Copyright &y& Elsevier]

Evolution equations for scalar density and orientation of fields of curved dislocations formulated in the framework of the continuum theory of moving dislocations serve as the starting point for development of a non-local dislocation-based constitutive relation for crystal plasticity, on the length scale intermediate between the phenomenological hardening laws of strain-gradient crystal plasticity and the explicit treatment of three-dimensional discrete dislocation dynamics. The key features of the proposed approach are the refined averaging in the continuum theory based on separation of single-valued dislocation fields, and the accounting for the line energy of the bowed dislocations which renders the theory non-local. [ABSTRACT FROM AUTHOR]

We develop an O(n³) algorithm for deciding if an n-vertex digraph has a subset of vertices with the property that each vertex of the graph has an even number of arcs into the subset. This algorithm allows us to give a combinatorial interpretation of GaussJordan and Gauss elimination on square boolean matrices. In addition to solving this independence-mod-2 (even) set existence problem we also give efficient algorithms for related domination-mod-2 (odd) set existence problems on digraphs. However, for each of the four combinations of these two properties we show that even though the existence problem on digraphs is tractable, the problems of deciding the existence of a set of size exactly k, larger than k, or smaller than k, for a given k, are all NP-complete for undirected graphs. [ABSTRACT FROM AUTHOR]

The notion of graph covers is a discretization of covering spaces introduced and deeply studied in topology. In discrete mathematics and theoretical computer science, they have attained a lot of attention from both the structural and complexity perspectives. Nonetheless, disconnected graphs were usually omitted from the considerations with the explanation that it is sufficient to understand coverings of the connected components of the target graph by components of the source one. However, different (but equivalent) versions of the definition of covers of connected graphs generalize to non-equivalent definitions for disconnected graphs. The aim of this paper is to summarize this issue and to compare three different approaches to covers of disconnected graphs: (1) locally bijective homomorphisms, (2) globally surjective locally bijective homomorphisms (which we call surjective covers), and (3) locally bijective homomorphisms which cover every vertex the same number of times (which we call equitable covers). The standpoint of our comparison is the complexity of deciding if an input graph covers a fixed target graph. We show that both surjective and equitable covers satisfy what certainly is a natural and welcome property: covering a disconnected graph is polynomial-time decidable if such it is for every connected component of the graph, and it is NP-complete if it is NP-complete for at least one of its components. We further argue that the third variant, equitable covers, is the most natural one, namely when considering covers of colored graphs. Moreover, the complexity of surjective and equitable covers differ from the fixed parameter complexity point of view. In line with the current trends in topological graph theory, as well as its applications in mathematical physics, we consider graphs in a very general sense: our graphs may contain loops, multiple edges and also semi-edges. Moreover, both vertices and edges may be colored, in which case the covering projection must respect the colors. We conclude the paper by a complete characterization of the complexity of covering 2-vertex colored graphs, and show that poly-time/NP-completeness dichotomy holds true for this case. We actually aim for a stronger dichotomy. All our polynomial-time algorithms work for arbitrary input graphs, while the NP-completeness theorems hold true even in the case of simple input graphs. [ABSTRACT FROM AUTHOR]

The article describes a model of interaction dynamics between a dislocation and dipolar dislocation loops. The interaction is essential for dipolar dislocation structure formation in early stages of a hardening process. For the description of the dislocation curve a direct parametric approach is employed whereas the loops are treated as rigid objects. The model equations are solved approximately by means of the finite-volume method. Physically interesting phenomena can be captured by the model provided the simulation covers long time periods. The strong interaction between the dislocation and the loops causes growing nonuniformity of distribution of discrete nodes along the dislocation curve. This effect is balanced by two proposed types of tangential redistribution of the discrete nodes. The redistribution is tested in simulations of loop clustering. [ABSTRACT FROM AUTHOR]

In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain multiple edges, loops, and semi-edges. A graph is called simple if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph H of valency greater than 2, deciding if an input graph covers H is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called List-H-Cover, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the List-H-Cover problem is NP-complete for every regular graph H of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of List-H-Cover for cubic graphs. [ABSTRACT FROM AUTHOR]

The game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in "Pursuing a fast robber on a graph", generalizing a well-known game of Cops and Robber which has robber speed 1. We answer their open question about the computational complexity of the game on interval graphs with ∞-fast robber, showing it to be polynomially decidable. We also generalize the concept of k -defensive domination introduced by Farley and Proskurowski in "Defensive Domination" to A -defensive domination and use it as a main tool in our proof. The generalization allows specifying arbitrary attacks and limiting the number of defenders of each vertex. While this problem is NP-complete even for split graphs, we show that A -defensive domination is decidable in polynomial time on interval graphs. [ABSTRACT FROM AUTHOR]

A graph G covers a graph H if there exists a locally bijective homomorphism from G to H . We deal with regular coverings in which this homomorphism is prescribed by an action of a semiregular subgroup Γ of Aut ( G ) ; so H ≅ G ∕ Γ . In this paper, we study the behavior of regular graph covering with respect to 1-cuts and2-cuts in G . We describe reductions which produce a series of graphs G = G 0 , … , G r such that G i + 1 is created from G i by replacing certain inclusion minimal subgraphs with colored edges. The process ends with a primitive graph G r which is either 3-connected, or a cycle, or K 2 . This reduction can be viewed as a non-trivial modification of reductions of Mac Lane (1937), Trachtenbrot (1958), Tutte (1966), Hopcroft and Tarjan (1973), Cuningham and Edmonds (1980), Walsh (1982), and others. A novel feature of our approach is that in each step all essential information about symmetries of G are preserved. A regular covering projection G 0 → H 0 induces regular covering projections G i → H i where H i is the i th quotient reduction of H 0 . This property allows to construct all possible quotients H 0 of G 0 from the possible quotients H r of G r . By applying this method to planar graphs, we give a proof of Negami’s Theorem (1988). Our structural results are also used in subsequent papers for regular covering testing when G is a planar graph and for an inductive characterization of the automorphism groups of planar graphs (see Babai (1973) as well). [ABSTRACT FROM AUTHOR]