1.
Graph theory

2010, 4th ed., Graduate texts in mathematics, ISBN 9783642142789, Volume 173., xviii, 436

Book

2.
Full Text
Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs

Journal of the ACM (JACM), ISSN 0004-5411, 11/2005, Volume 52, Issue 6, pp. 866 - 893

...) . Our results apply to a broad family of graph problems, called bidimensional problems , which includes many domination and problems such as vertex cover, feedback vertex set, minimum maximal matching...

map graph | domination | planar graph | ( k,r )-center | fixed-parameter algorithms | Domination | Fixed-parameter algorithms | Planar graph | (k, r)-center | Map graph | algorithms | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | SINGLE-CROSSING GRAPHS | TREEWIDTH | COMPUTER SCIENCE, INFORMATION SYSTEMS | TREE-WIDTH | DOMINATING SET | COMPUTER SCIENCE, SOFTWARE ENGINEERING | R)-CENTER | design | COMPLEXITY | PLANAR GRAPHS | MINERS | COMPUTER SCIENCE, THEORY & METHODS | theory | Studies | Graph algorithms | Algorithms | Categories | Running | Constants | Graphs | Polynomials | Graph theory | Combinatorial analysis

map graph | domination | planar graph | ( k,r )-center | fixed-parameter algorithms | Domination | Fixed-parameter algorithms | Planar graph | (k, r)-center | Map graph | algorithms | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | SINGLE-CROSSING GRAPHS | TREEWIDTH | COMPUTER SCIENCE, INFORMATION SYSTEMS | TREE-WIDTH | DOMINATING SET | COMPUTER SCIENCE, SOFTWARE ENGINEERING | R)-CENTER | design | COMPLEXITY | PLANAR GRAPHS | MINERS | COMPUTER SCIENCE, THEORY & METHODS | theory | Studies | Graph algorithms | Algorithms | Categories | Running | Constants | Graphs | Polynomials | Graph theory | Combinatorial analysis

Journal Article

Theoretical computer science, ISSN 0304-3975, 2018, Volume 745, pp. 36 - 52

We introduce the family of k-gap-planar graphs for k≥0, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings...

k-quasiplanar graphs | Complete graphs | Beyond planarity k-gap-planar graphs | k-planar graphs | Density results | Recognition problem | LINEAR-TIME | NUMBER | CROSSINGS | EDGES | COMPUTER SCIENCE, THEORY & METHODS | 1-PLANARITY

k-quasiplanar graphs | Complete graphs | Beyond planarity k-gap-planar graphs | k-planar graphs | Density results | Recognition problem | LINEAR-TIME | NUMBER | CROSSINGS | EDGES | COMPUTER SCIENCE, THEORY & METHODS | 1-PLANARITY

Journal Article

Algorithmica, ISSN 0178-4617, 4/2016, Volume 74, Issue 4, pp. 1293 - 1320

A graph is outer 1-planar (o1p) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once...

Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Graph parameters | Mathematics of Computing | Embeddings and drawings | Planar and outerplanar graphs | 1-Planarity | Computer Science | Theory of Computation | Algorithm Analysis and Problem Complexity | Density | COMPUTER SCIENCE, SOFTWARE ENGINEERING | CROSSING NUMBER | MATHEMATICS, APPLIED | EVERY PLANAR MAP | RECTILINEAR DRAWINGS | HARD | ALGORITHMS

Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Graph parameters | Mathematics of Computing | Embeddings and drawings | Planar and outerplanar graphs | 1-Planarity | Computer Science | Theory of Computation | Algorithm Analysis and Problem Complexity | Density | COMPUTER SCIENCE, SOFTWARE ENGINEERING | CROSSING NUMBER | MATHEMATICS, APPLIED | EVERY PLANAR MAP | RECTILINEAR DRAWINGS | HARD | ALGORITHMS

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 01/2017, Volume 217, pp. 304 - 317

...; we call any such graph an a-graph. We state an a-graph coloring problem equivalent to the 4-color problem and then derive a coloring condition that a minimal a-graph counterexample must satisfy, expressing it in terms of equivalence...

Minimal counterexample | Equivalence class | Birkhoff diamond | Kempe exchange | 4-color problem | MATHEMATICS, APPLIED | EVERY PLANAR MAP

Minimal counterexample | Equivalence class | Birkhoff diamond | Kempe exchange | 4-color problem | MATHEMATICS, APPLIED | EVERY PLANAR MAP

Journal Article

Journal of mechanical design (1990), ISSN 1050-0472, 01/2018, Volume 140, Issue 1

.... The graph theory has been proved to be an effective tool to synthesize and analyze PGTs. This paper aims to propose a new graph model, which has some merits relative to the existing ones, to represent the structure of PGTs...

displacement graph | ENUMERATION | ENGINEERING, MECHANICAL | structure synthesis | rotation graph | METHODOLOGY | PLANAR KINEMATIC CHAINS | planetary gear train | STRUCTURAL SYNTHESIS | TOPOLOGICAL ANALYSIS | LOOPS | pseudo-isomorphic graph | DISPLACEMENT ISOMORPHISM

displacement graph | ENUMERATION | ENGINEERING, MECHANICAL | structure synthesis | rotation graph | METHODOLOGY | PLANAR KINEMATIC CHAINS | planetary gear train | STRUCTURAL SYNTHESIS | TOPOLOGICAL ANALYSIS | LOOPS | pseudo-isomorphic graph | DISPLACEMENT ISOMORPHISM

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 07/2020, Volume 281, pp. 96 - 105

The problem of the intersection of longest paths consists in determining the size of a smallest subset of vertices of a graph such that every longest path contains at least one vertex of the set...

MATHEMATICS, APPLIED | NONEMPTY INTERSECTION | PLANAR

MATHEMATICS, APPLIED | NONEMPTY INTERSECTION | PLANAR

Journal Article

Journal of combinatorial theory. Series B, ISSN 0095-8956, 01/2017, Volume 122, pp. 741 - 756

For a loopless multigraph G, the fractional arboricityArb(G) is the maximum of |E(H)||V(H)|−1 over all subgraphs H with at least two vertices. Generalizing the...

Graph decomposition | Sparse graph | Arboricity | Fractional arboricity | Forest | Discharging method | Nash-Williams Arboricity Formula | Nine Dragon Tree Conjecture | MATHEMATICS | PLANAR GRAPHS | GIRTH | Forests and forestry

Graph decomposition | Sparse graph | Arboricity | Fractional arboricity | Forest | Discharging method | Nash-Williams Arboricity Formula | Nine Dragon Tree Conjecture | MATHEMATICS | PLANAR GRAPHS | GIRTH | Forests and forestry

Journal Article

Theoretical computer science, ISSN 0304-3975, 08/2015, Volume 593, pp. 160 - 164

Let G be any connected graph on n vertices, n≥2. Let k be any positive integer. Suppose that a fire breaks out at some vertex of G...

Firefighter problem | Planar graph | Surviving rate | COMPUTER SCIENCE, THEORY & METHODS | Integers | Firefighters | Breaking | Fires | Graphs | Spreads | Mathematical models | Graph theory

Firefighter problem | Planar graph | Surviving rate | COMPUTER SCIENCE, THEORY & METHODS | Integers | Firefighters | Breaking | Fires | Graphs | Spreads | Mathematical models | Graph theory

Journal Article

Algorithmica, ISSN 0178-4617, 8/2018, Volume 80, Issue 8, pp. 2260 - 2285

Bus graphs are used for the visualization of hypergraphs, for example in VLSI design...

Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Mathematics of Computing | Bus graphs as hypergraphs | Computer Science | Planar graphs | Theory of Computation | Graph visualization | Algorithm Analysis and Problem Complexity | Efficient algorithms | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED | Very-large-scale integration | Visualization (Computers)

Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Mathematics of Computing | Bus graphs as hypergraphs | Computer Science | Planar graphs | Theory of Computation | Graph visualization | Algorithm Analysis and Problem Complexity | Efficient algorithms | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED | Very-large-scale integration | Visualization (Computers)

Journal Article

Journal of combinatorial theory. Series B, ISSN 0095-8956, 2015, Volume 110, pp. 79 - 89

A k-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into k sets such that no two edges that are in the same set are nested with respect to the vertex ordering...

Queue number | Graph separators | Track number | Graph layouts | 3D grid drawings | STACK | MATHEMATICS | DIRECTED ACYCLIC GRAPHS | NUMBER | QUEUE LAYOUTS | PLANAR GRAPHS | PAGENUMBER

Queue number | Graph separators | Track number | Graph layouts | 3D grid drawings | STACK | MATHEMATICS | DIRECTED ACYCLIC GRAPHS | NUMBER | QUEUE LAYOUTS | PLANAR GRAPHS | PAGENUMBER

Journal Article

Journal of Graph Theory, ISSN 0364-9024, 07/2015, Volume 79, Issue 3, pp. 178 - 212

A signed graph [G,Σ] is a graph G together with an assignment of signs + and − to all the edges of G where Σ...

homomorphism | signed graph | coloring | minor | Hadwiger's conjecture | PROJECTIVE CUBES | COLORINGS | MATHEMATICS | EDGE-COLORED GRAPHS | PLANAR GRAPHS | FLOWS | CONJECTURE | Computer Science | Discrete Mathematics

homomorphism | signed graph | coloring | minor | Hadwiger's conjecture | PROJECTIVE CUBES | COLORINGS | MATHEMATICS | EDGE-COLORED GRAPHS | PLANAR GRAPHS | FLOWS | CONJECTURE | Computer Science | Discrete Mathematics

Journal Article

International journal of machine learning and cybernetics, ISSN 1868-808X, 2014, Volume 7, Issue 4, pp. 653 - 664

In this paper, interval-valued fuzzy planar graphs are defined and several properties are studied...

Engineering | Interval-valued fuzzy planar graphs | Pattern Recognition | Interval-valued fuzzy multigraphs | Computational Intelligence | Control, Robotics, Mechatronics | Artificial Intelligence (incl. Robotics) | Statistical Physics, Dynamical Systems and Complexity | Interval-valued fuzzy graphs | Systems Biology | Interval-valued fuzzy | COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE | ARCS

Engineering | Interval-valued fuzzy planar graphs | Pattern Recognition | Interval-valued fuzzy multigraphs | Computational Intelligence | Control, Robotics, Mechatronics | Artificial Intelligence (incl. Robotics) | Statistical Physics, Dynamical Systems and Complexity | Interval-valued fuzzy graphs | Systems Biology | Interval-valued fuzzy | COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE | ARCS

Journal Article

Discrete mathematics, ISSN 0012-365X, 2009, Volume 309, Issue 17, pp. 5381 - 5392

In this paper, we consider the intersection graph
G
(
R
)
of nontrivial left ideals of a ring
R...

Unordered factorization | Hamiltonian graph | Ideal of a ring | Complete graph | Ring | Planar graph | Connected graph | Bipartite graph | Intersection graph | Eulerian graph | Cycle | Artinian ring | COMMUTATIVE RING | ZERO-DIVISOR GRAPH | MATHEMATICS

Unordered factorization | Hamiltonian graph | Ideal of a ring | Complete graph | Ring | Planar graph | Connected graph | Bipartite graph | Intersection graph | Eulerian graph | Cycle | Artinian ring | COMMUTATIVE RING | ZERO-DIVISOR GRAPH | MATHEMATICS

Journal Article

Journal of Combinatorial Optimization, ISSN 1382-6905, 11/2014, Volume 28, Issue 4, pp. 774 - 786

Let
$$d_1, d_2,\dots ,d_k$$
be
$$k$$
non-negative integers. A graph
$$G$$
is
$$(d_1,d_2,\ldots ,d_k)$$
-colorable, if the vertex set...

Improper coloring | Convex and Discrete Geometry | Operations Research/Decision Theory | Planar graph | Mathematics | Theory of Computation | Steinberg’s conjecture | Mathematical Modeling and Industrial Mathematics | Combinatorics | Optimization | COLORINGS | MATHEMATICS, APPLIED | Steinberg's conjecture | COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS

Improper coloring | Convex and Discrete Geometry | Operations Research/Decision Theory | Planar graph | Mathematics | Theory of Computation | Steinberg’s conjecture | Mathematical Modeling and Industrial Mathematics | Combinatorics | Optimization | COLORINGS | MATHEMATICS, APPLIED | Steinberg's conjecture | COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS

Journal Article

Journal of Combinatorial Optimization, ISSN 1382-6905, 10/2016, Volume 32, Issue 3, pp. 927 - 940

A list assignment of a graph G is a function L that assigns a list L(v) of colors to each vertex
$$v\in V(G)$$
v
∈
V
(
G
)
. An
$$(L,d)^*$$
(
L
,
d...

Convex and Discrete Geometry | Improper choosability | Planar graphs | Mathematics | Theory of Computation | Mathematical Modeling and Industrial Mathematics | Operation Research/Decision Theory | Combinatorics | Optimization | Cycle | COLORINGS | MATHEMATICS, APPLIED | COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS

Convex and Discrete Geometry | Improper choosability | Planar graphs | Mathematics | Theory of Computation | Mathematical Modeling and Industrial Mathematics | Operation Research/Decision Theory | Combinatorics | Optimization | Cycle | COLORINGS | MATHEMATICS, APPLIED | COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS

Journal Article

Journal of the ACM (JACM), ISSN 0004-5411, 12/2019, Volume 66, Issue 6, pp. 1 - 31

We prove that the Weisfeiler--Leman (WL) dimension of the class of all finite planar graphs is at most...

First-order logic with counting | isomorphism testing | planar graphs | Weisfeiler--Leman algorithm | COMPUTER SCIENCE, SOFTWARE ENGINEERING | ISOMORPHISM | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | COMPLEXITY | COMPUTER SCIENCE, INFORMATION SYSTEMS | COMPUTER SCIENCE, THEORY & METHODS | Weisfeiler Leman algorithm | PARALLEL | Algorithms | Apexes | Upper bounds | Isomorphism | Graphs | Orbits | Graph theory | Automorphisms

First-order logic with counting | isomorphism testing | planar graphs | Weisfeiler--Leman algorithm | COMPUTER SCIENCE, SOFTWARE ENGINEERING | ISOMORPHISM | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | COMPLEXITY | COMPUTER SCIENCE, INFORMATION SYSTEMS | COMPUTER SCIENCE, THEORY & METHODS | Weisfeiler Leman algorithm | PARALLEL | Algorithms | Apexes | Upper bounds | Isomorphism | Graphs | Orbits | Graph theory | Automorphisms

Journal Article

Journal of Combinatorial Optimization, ISSN 1382-6905, 5/2017, Volume 33, Issue 4, pp. 1354 - 1364

.... A graph G is
$$(c_{1},c_{2},\ldots ,c_{k})$$
(
c
1
,
c
2
,
…
,
c
k
)
-colorable if the vertex set can be partitioned into k sets
$$V_{1},V_{2},\ldots ,V_{k}$$
V
1
,
V
2...

Improper coloring | Convex and Discrete Geometry | Planar graphs | Mathematics | Theory of Computation | Mathematical Modeling and Industrial Mathematics | Operation Research/Decision Theory | Combinatorics | Optimization | Cycle | MATHEMATICS, APPLIED | COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS | LENGTH | CYCLES

Improper coloring | Convex and Discrete Geometry | Planar graphs | Mathematics | Theory of Computation | Mathematical Modeling and Industrial Mathematics | Operation Research/Decision Theory | Combinatorics | Optimization | Cycle | MATHEMATICS, APPLIED | COMPUTER SCIENCE, INTERDISCIPLINARY APPLICATIONS | LENGTH | CYCLES

Journal Article

Algorithmica, ISSN 1432-0541, 2018, Volume 81, Issue 5, pp. 1818 - 1843

We characterize 4-map graphs as kite-augmented 1-planar graphs and show that they can be recognized in cubic time...

Computer Systems Organization and Communication Networks | Algorithms | Maps | Mathematics of Computing | Computer Science | Planar graphs | 1-Planar graphs | Theory of Computation | Graph algorithms | Algorithm Analysis and Problem Complexity | Map graphs | Data Structures and Information Theory | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED

Computer Systems Organization and Communication Networks | Algorithms | Maps | Mathematics of Computing | Computer Science | Planar graphs | 1-Planar graphs | Theory of Computation | Graph algorithms | Algorithm Analysis and Problem Complexity | Map graphs | Data Structures and Information Theory | COMPUTER SCIENCE, SOFTWARE ENGINEERING | MATHEMATICS, APPLIED

Journal Article

Applied mathematics and computation, ISSN 0096-3003, 2018, Volume 325, pp. 246 - 251

A strong edge coloring of a graph is a proper edge coloring in which every color class is an induced matching...

Odd graph | Strong chromatic index | Strong edge coloring | Planar graphs | Maximum average degree | MATHEMATICS, APPLIED | GIRTH

Odd graph | Strong chromatic index | Strong edge coloring | Planar graphs | Maximum average degree | MATHEMATICS, APPLIED | GIRTH

Journal Article

No results were found for your search.

Cannot display more than 1000 results, please narrow the terms of your search.