Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Computer Program
Connected Graph
Efficient Algorithm
Electrical Network
Machine Translation
Pattern Recognition
Related Publications
(1)
Isomorphism of planar graphs (working paper)
Subscribe
Academic
Publications
A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs
A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs,10.1109/TCT.1966.1082573,IEEE Transactions on Circuit T
Edit
A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected Graphs
(
Citations: 25
)
BibTex

RIS

RefWorks
Download
LOUIS WEINBERG
A problem that arises in many practical applications of linear graphs and in some purely mathematical applications is the determination of the isomorphism of two given graphs; such applications include the automatic retrieval of information,
machine translation
of languages, pipeline and electric networks, pattern recognition, graphtheoretic enumeration problems, the fourcolor conjecture, and the problem of "squaring the rectangle." Up to the present time only heuristic programs have been developed for solving this problem for general graphs. In this paper, a solution for a class of graphs is given in terms of a simple and computationally efficient algorithm, which is ideally suited for computer programming; a program in MAD language has been written but has not yet been run. The class of graphs considered are planar and triply connected; this class arises, for example, in the fourcolor problem and in the problem of squaring the rectangle. The algorithm is applicable to both directed and undirected graphs and to simple graphs and multigraphs. The algorithm is based on Trémaux's procedure for generating an Euler path in a graph. Application of the algorithm to a plane triply
connected graph
yields a set of vector codes which are ordered lexicographically in a code matrix.
Journal:
IEEE Transactions on Circuit Theory
, vol. 13, no. 2, pp. 142148, 1966
DOI:
10.1109/TCT.1966.1082573
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
Citation Context
(13)
...Weinberg [
Wei66
] presented an O(n2) algorithm for testing isomorphism...
Samir Datta
,
et al.
Planar Graph Isomorphism is in LogSpace
...In 1966, Weinberg [
Wei66
] presented an O(n2)algorithm for testing...
...Weinberg [
Wei66
] used these embeddings to compute a code for a graph, such that isomorphic graphs will have the same code...
...In 1966, Weinberg [
Wei66
] presented an O(n2) algorithm for testing isomorphism of...
Thomas Thierauf
,
et al.
The Isomorphism Problem for Planar 3Connected Graphs is in Unambiguous...
...In 1966, Weinberg [
71
] gave a very simple O(n2) algorithm...
...Hopcroft and Tarjan [32], and Weinberg [
71
]...
...As pointed out by Weinberg [
71
], there is an easy algorithm for this problem when the surface is planar...
Kenichi Kawarabayashi
,
et al.
Graph and map isomorphism and all polyhedral embeddings in linear time
...Loworder polynomialtime methods [35, 36,
64
] are also known for planar graphs...
Xiaoyi Jiang
,
et al.
Graph Matching
...In the next section, we give definitions and Weinberg’s [
48
] concept of constructing codes for triconnected graphs...
...In 1966, Weinberg [
48
] presented an O(n2) algorithm for testing isomorphism of planar triconnected graphs...
...Every planar triconnected graph with m edges and n vertices has 4m codes of length 2m+1 [
48
]...
...CV [eV ]=FINDCODE(twin edge of(eV ), skeleton(º), A, T ) 3: end for 4: C.append( ”R(” ) 5: Apply Weinberg’s [
48
] procedure to find code associated with ein going right...
...Proof In the proof we refer to Weinberg’s paper [
48
]...
...It is also true that G1 and G2 are isomorphic if and only if any row of M1 equals any row of M2 [
48
]...
...The Eulerian path started from the initial edge is deterministic in both embeddings of the skeleton, because by the property of triconnected graphs [
48
], the set of edges incident to a vertex has a unique order around the vertex...
Jacek P. Kukluk
,
et al.
Algorithm and Experiments in Testing Planar Graphs for Isomorphism
References
(2)
Linear Graphs and Electrical Networks
(
Citations: 204
)
S. Seshu
,
M. B. Reed
Published in 1961.
Mathematical Recreations and Essays
(
Citations: 92
)
Unknown
Journal:
Nature
, vol. 72, no. 1868, pp. 364365, 1905
Sort by:
Citations
(25)
Planar Graph Isomorphism is in LogSpace
(
Citations: 8
)
Samir Datta
,
Nutan Limaye
,
Prajakta Nimbhorkar
,
Thomas Thierauf
,
Fabian Wagner
Conference:
Annual IEEE Conference on Computational Complexity  CCC
, vol. 16, pp. 203214, 2009
The Isomorphism Problem for Planar 3Connected Graphs is in Unambiguous Logspace
(
Citations: 11
)
Thomas Thierauf
,
Fabian Wagner
Journal:
Theory of Computing Systems / Mathematical Systems Theory  MST
, vol. abs/0802.2, no. 3, pp. 633644, 2008
Graph and map isomorphism and all polyhedral embeddings in linear time
(
Citations: 11
)
Kenichi Kawarabayashi
,
Bojan Mohar
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 471480, 2008
3connected Planar Graph Isomorphism is in Logspace
(
Citations: 5
)
Samir Datta
,
Nutan Limaye
,
Prajakta Nimbhorkar
Journal:
Computing Research Repository  CORR
, vol. abs/0806.1, pp. 155162, 2008
A Logspace Algorithm for Canonization of Planar Graphs
(
Citations: 3
)
Samir Datta
,
Nutan Limaye
,
Prajakta Nimbhorkar
,
Thomas Thierauf
,
Fabian Wagner
Journal:
Computing Research Repository  CORR
, vol. abs/0809.2, 2008