Discrete Mathematics and Theoretical Computer Science, ISSN 1462-7264, 05/2019, Volume 21 no. 1, ICGT 2018

We prove that, given a closure function the smallest preimage of a closed set can be calculated in polynomial time in the number of closed sets. This implies...

Computer Science | Computational Complexity

Computer Science | Computational Complexity

Journal Article

DISCRETE & COMPUTATIONAL GEOMETRY, ISSN 0179-5376, 03/2020, Volume 63, Issue 2, pp. 377 - 417

We give two graph theoretical characterizations of tope graphs of (complexes of) oriented matroids. The first is in terms of excluded partial cube minors, the...

MATHEMATICS | Lopsided sets | Partial cubes | COMPUTER SCIENCE, THEORY & METHODS | Complexes of oriented matroids | Oriented matroids | Tope graphs | ARRANGEMENTS | Graphs | Graph theory | Polynomials | Algorithms | Computational Geometry | Computer Science | Discrete Mathematics | Computational Complexity

MATHEMATICS | Lopsided sets | Partial cubes | COMPUTER SCIENCE, THEORY & METHODS | Complexes of oriented matroids | Oriented matroids | Tope graphs | ARRANGEMENTS | Graphs | Graph theory | Polynomials | Algorithms | Computational Geometry | Computer Science | Discrete Mathematics | Computational Complexity

Journal Article

Discrete Mathematics, ISSN 0012-365X, 04/2020, Volume 343, Issue 4, p. 111678

Journal Article

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, 2012, Volume 7434, pp. 323 - 334

Journal Article

Journal of Combinatorial Theory, Series B, ISSN 0095-8956, 01/2019, Volume 134, pp. 88 - 109

Refining a classical proof of Whitney, we show that any 4-connected planar triangulation can be decomposed into a Hamiltonian path and two trees. Therefore,...

Decomposition into trees | Planar graphs | MATHEMATICS | FORESTS | SPARSE GRAPHS | Computer Science

Decomposition into trees | Planar graphs | MATHEMATICS | FORESTS | SPARSE GRAPHS | Computer Science

Journal Article

International Journal of Game Theory, ISSN 0020-7276, 10/2019

In chomp on graphs, two players alternatingly pick an edge or a vertex from a graph. The player that cannot move any more loses. The questions one wants to...

Computer Science | Discrete Mathematics

Computer Science | Discrete Mathematics

Journal Article

Discrete Mathematics, ISSN 0012-365X, 02/2016, Volume 339, Issue 2, pp. 866 - 876

We prove that the combinatorial optimization problem of determining the hull number of a partial cube is NP-complete. This makes partial cubes the minimal...

Algorithmic complexity | Poset dimension | Partial cube | Hull-number | Upper locally distributive lattice | Topological representation | MATHEMATICS | ORIENTED MATROIDS | COMPLEXITY | LATTICES | GRAPHS | Computer Science

Algorithmic complexity | Poset dimension | Partial cube | Hull-number | Upper locally distributive lattice | Topological representation | MATHEMATICS | ORIENTED MATROIDS | COMPLEXITY | LATTICES | GRAPHS | Computer Science

Journal Article

Discrete and Computational Geometry, ISSN 0179-5376, 10/2018, Volume 60, Issue 3, pp. 698 - 719

In this paper we investigate the number of integer points lying in dilations of lattice path matroid polytopes. We give a characterization of such points as...

Distributive polytope | Lattice path matroid | Matroid base polytope | Ehrhart polynomial | MATHEMATICS | NEGGERS | STANLEY | COMPUTER SCIENCE, THEORY & METHODS | Computer science | Polytopes | Polynomials | Computer Science

Distributive polytope | Lattice path matroid | Matroid base polytope | Ehrhart polynomial | MATHEMATICS | NEGGERS | STANLEY | COMPUTER SCIENCE, THEORY & METHODS | Computer science | Polytopes | Polynomials | Computer Science

Journal Article

Discrete Mathematics, ISSN 0012-365X, 06/2017, Volume 340, Issue 6, pp. 1151 - 1153

In this note we determine the set of expansions such that a partial cube is planar if and only if it arises by a sequence of such expansions from a single...

Partial cubes | Expansions | Planar graphs | MATHEMATICS | CONVEXITY | GRAPHS | Computer Science

Partial cubes | Expansions | Planar graphs | MATHEMATICS | CONVEXITY | GRAPHS | Computer Science

Journal Article

European Journal of Combinatorics, ISSN 0195-6698, 02/2019, Volume 76, pp. 27 - 36

We discuss conjectures on Hamiltonicity in cubic graphs (Tait, Barnette, Tutte), on the dichromatic number of planar oriented graphs (Neumann-Lara), and on...

MATHEMATICS | Computer Science | Discrete Mathematics

MATHEMATICS | Computer Science | Discrete Mathematics

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 06/2016, Volume 206, pp. 48 - 55

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: ▪, ▪,▪ and ▪. A k-bend path is a simple...

Co-planar graphs | Planar 3-trees | [formula omitted]-bend [formula omitted]-graphs | Intersection graphs | Segment graphs | k-bend VPG-graphs | MATHEMATICS, APPLIED | NUMBER | REPRESENTATIONS | CLIQUE PROBLEM | PATHS | COPLANAR GRAPHS | Subdivisions | Horizontal | Planes | Images | Segments | Graphs | Complement | Graphical representations | Computer Science

Co-planar graphs | Planar 3-trees | [formula omitted]-bend [formula omitted]-graphs | Intersection graphs | Segment graphs | k-bend VPG-graphs | MATHEMATICS, APPLIED | NUMBER | REPRESENTATIONS | CLIQUE PROBLEM | PATHS | COPLANAR GRAPHS | Subdivisions | Horizontal | Planes | Images | Segments | Graphs | Complement | Graphical representations | Computer Science

Journal Article

Discrete Mathematics, ISSN 0012-365X, 02/2016, Volume 339, Issue 2, pp. 745 - 758

We consider the problem of covering an input graph H with graphs from a fixed covering class G. The classical covering number of H with respect to G is the...

Caterpillar arboricity | Star arboricity | Graph covering | Track number | Interval number | Linear arboricity | MATHEMATICS | EDGE-INTERSECTION GRAPHS | PACKING | PLANAR | THICKNESS | Computer Science

Caterpillar arboricity | Star arboricity | Graph covering | Track number | Interval number | Linear arboricity | MATHEMATICS | EDGE-INTERSECTION GRAPHS | PACKING | PLANAR | THICKNESS | Computer Science

Journal Article

Journal of Computational Geometry, ISSN 1920-180X, 2019, Volume 10, Issue 1, pp. 127 - 164

We propose a simple generalization of Schnyder woods from the plane to maps on orientable surfaces of higher genus. This is done in the language of angle...

Computer Science | Discrete Mathematics

Computer Science | Discrete Mathematics

Journal Article

Journal of Graph Theory, ISSN 0364-9024, 12/2016, Volume 83, Issue 4, pp. 392 - 405

We prove that any triangulation of a surface different from the sphere and the projective plane admits an orientation without sinks such that every vertex has...

orientations | triangulations | surfaces | MATHEMATICS | Computer Science

orientations | triangulations | surfaces | MATHEMATICS | Computer Science

Journal Article

Combinatorica, ISSN 0209-9683, 8/2018, Volume 38, Issue 4, pp. 861 - 885

Las Vergnas and Hamidoune studied the number of circuits needed to determine an oriented matroid. In this paper we investigate this problem and some new...

52C40 | Mathematics, general | 05B35 | Mathematics | Combinatorics | MATHEMATICS | PACKING | COVERINGS | MUTATIONS | GRAPHS

52C40 | Mathematics, general | 05B35 | Mathematics | Combinatorics | MATHEMATICS | PACKING | COVERINGS | MUTATIONS | GRAPHS

Journal Article

Journal of Graph Theory, ISSN 0364-9024, 05/2017, Volume 85, Issue 1, pp. 288 - 291

Given a directed graph, an acyclic set is a set of vertices inducing a directed subgraph with no directed cycle. In this note, we show that for all integers...

acyclic set | feedback vertex set | planar digraphs | MATHEMATICS | Computer Science | Discrete Mathematics

acyclic set | feedback vertex set | planar digraphs | MATHEMATICS | Computer Science | Discrete Mathematics

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 04/2014, Volume 167, pp. 144 - 162

We investigate edge-intersection graphs of paths in the plane grid, regarding a parameter called the bend-number, i.e., every vertex is represented by a grid...

Grid paths | Intersection graphs | MATHEMATICS, APPLIED | INTERVAL NUMBER | CATERPILLAR ARBORICITY | STAR ARBORICITY | Lower bounds | Graphs | Bends | Planes | Mathematical analysis | Recognition | Computer Science

Grid paths | Intersection graphs | MATHEMATICS, APPLIED | INTERVAL NUMBER | CATERPILLAR ARBORICITY | STAR ARBORICITY | Lower bounds | Graphs | Bends | Planes | Mathematical analysis | Recognition | Computer Science

Journal Article

Electronic Notes in Discrete Mathematics, ISSN 1571-0653, 2009, Volume 34, pp. 9 - 13

Starting from the chip-firing game of Björner and Lovász we consider a generalization to vector addition systems that still admit algebraic structures as...

membership problem | chip-firing game | upper locally distributive lattice | antimatroid | vector addition language

membership problem | chip-firing game | upper locally distributive lattice | antimatroid | vector addition language

Journal Article

Semigroup Forum, ISSN 0037-1912, 2/2016, Volume 92, Issue 1, pp. 142 - 157

In 1896 Heinrich Maschke characterized planar finite groups, that is groups which admit a generating system such that the resulting Cayley graph is planar. In...

Right group | Planar | Mathematics | Semigroup | Algebra | Cayley graph | MATHEMATICS | SEMIGROUPS | CAYLEY-GRAPHS | Computer Science

Right group | Planar | Mathematics | Semigroup | Algebra | Cayley graph | MATHEMATICS | SEMIGROUPS | CAYLEY-GRAPHS | Computer Science

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 12/2014, Volume 179, pp. 109 - 119

The bend-numberb(G) of a graph G is the minimum k such that G may be represented as the edge intersection graph of a set of grid paths with at most k bends. We...

Bend-number | EPG-representation | Outerplanar graph | Planar graph | MATHEMATICS, APPLIED | STAR | EDGE-INTERSECTION GRAPHS | PATHS | INTERVAL NUMBER | ARBORICITY | Computer Science

Bend-number | EPG-representation | Outerplanar graph | Planar graph | MATHEMATICS, APPLIED | STAR | EDGE-INTERSECTION GRAPHS | PATHS | INTERVAL NUMBER | ARBORICITY | Computer Science

Journal Article

No results were found for your search.

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