On the generation of topological (nk)-configurations

Jürgen Bokowski; Vincent Pilaud

On the generation of topological (n_k)-configurations

Jürgen Bokowski
, Vincent Pilaud

Research output: Contribution to conference › Paper › peer-review

Abstract

An (n_k)-configuration is a set of n points and n lines in the projective plane such that the point { line incidence graph is k-regular. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines or just combinatorial lines. We provide an algorithm for generating all combinatorial (n _k)-configurations that admit a topological realization, for given n and k. This is done without enumerating first all combinatorial (n _k)-configurations. Among other results, our algorithm enables us to con- firm, in just one hour with a Java code of the second author, a satisfiability result of Lars Schewe in [11], obtained after several months of CPU-time.

Original language	English
Publication status	Published - 1 Dec 2011
Externally published	Yes
Event	23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada Duration: 10 Aug 2011 → 12 Aug 2011

Conference

Conference	23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Country/Territory	Canada
City	Toronto, ON
Period	10/08/11 → 12/08/11

Cite this

@conference{d052701068334b74a73c717b6b78b162,

title = "On the generation of topological (nk)-configurations",

abstract = "An (nk)-configuration is a set of n points and n lines in the projective plane such that the point \{ line incidence graph is k-regular. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines or just combinatorial lines. We provide an algorithm for generating all combinatorial (n k)-configurations that admit a topological realization, for given n and k. This is done without enumerating first all combinatorial (n k)-configurations. Among other results, our algorithm enables us to con- firm, in just one hour with a Java code of the second author, a satisfiability result of Lars Schewe in [11], obtained after several months of CPU-time.",

author = "J{\"u}rgen Bokowski and Vincent Pilaud",

year = "2011",

month = dec,

day = "1",

language = "English",

note = "23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 ; Conference date: 10-08-2011 Through 12-08-2011",

}

TY - CONF

T1 - On the generation of topological (nk)-configurations

AU - Bokowski, Jürgen

AU - Pilaud, Vincent

PY - 2011/12/1

Y1 - 2011/12/1

N2 - An (nk)-configuration is a set of n points and n lines in the projective plane such that the point { line incidence graph is k-regular. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines or just combinatorial lines. We provide an algorithm for generating all combinatorial (n k)-configurations that admit a topological realization, for given n and k. This is done without enumerating first all combinatorial (n k)-configurations. Among other results, our algorithm enables us to con- firm, in just one hour with a Java code of the second author, a satisfiability result of Lars Schewe in [11], obtained after several months of CPU-time.

AB - An (nk)-configuration is a set of n points and n lines in the projective plane such that the point { line incidence graph is k-regular. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines or just combinatorial lines. We provide an algorithm for generating all combinatorial (n k)-configurations that admit a topological realization, for given n and k. This is done without enumerating first all combinatorial (n k)-configurations. Among other results, our algorithm enables us to con- firm, in just one hour with a Java code of the second author, a satisfiability result of Lars Schewe in [11], obtained after several months of CPU-time.

UR - https://www.scopus.com/pages/publications/84882983669

M3 - Paper

AN - SCOPUS:84882983669

T2 - 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011

Y2 - 10 August 2011 through 12 August 2011

ER -

On the generation of topological (n_k)-configurations

Abstract

Conference

Other files and links

Fingerprint

Cite this