Worboys, M.F. (2013) Using bigraphs to model topological graphs embedded in orientable surfaces. Theoretical Computer Science, 484. pp. 56-69. ISSN 0304-3975 (doi:10.1016/j.tcs.2013.02.018)

Full text not available from this repository. (Request a copy)

Abstract

Natural and artificial environments, at scales ranging from cellular to geographic, have complex and changing spatial structures based on regions, as well as being inhabited by a multiplicity of dynamic entities. Milner’s theory of bigraphs provides a formal design tool for dynamic and complex systems. However, bigraphs have rather limited explicit capability to represent spatial properties and relationships, being only equipped with a place graph that can express the containment relation between locations. This paper develops constructions that provide explicit bigraph types for representing complex two-dimensional spatial configurations, and shows that such representations are unique up to topological equivalence. In particular, we show how bigraphs can uniquely represent topological graphs embedded in compact, orientable surfaces in ℜn, as well as in the Euclidean plane. © 2013 Elsevier B.V.

Item Type:	Article
Additional Information:	[1] First published: 6 May 2013. [2] Published as: Theoretical Computer Science, (2013), Vol. 484, pp. 56–69.
Uncontrolled Keywords:	bigraph, combinatorial map, spatial modeling, graph embedding
Subjects:	Q Science > QA Mathematics
Faculty / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Last Modified:	04 Mar 2022 13:08
URI:	http://gala.gre.ac.uk/id/eprint/10088

Actions (login required)

View Item