A compact adjacency-based topological data structure for finite element mesh representation

Waldemar Celes, Glaucio H. Paulino, Rodrigo Espinha

Research output: Contribution to journalArticlepeer-review


This paper presents a novel compact adjacency-based topological data structure for finite element mesh representation. The proposed data structure is designed to support, under the same framework, both two- and three-dimensional meshes, with any type of elements defined by templates of ordered nodes. When compared to other proposals, our data structure reduces the required storage space while being 'complete', in the sense that it preserves the ability to retrieve all topological adjacency relationships in constant time or in time proportional to the number of retrieved entities. Element and node are the only entities explicitly represented. Other topological entities, which include facet, edge, and vertex, are implicitly represented. In order to simplify accessing topological adjacency relationships, we also define and implicitly represent oriented entities, associated to the use of facets, edges, and vertices by an element. All implicit entities are represented by concrete types, being handled as values, which avoid usual problems encountered in other reduced data structures when performing operations such as entity enumeration and attribute attachment. We also extend the data structure with the use of 'reverse indices', which improves performance for extracting adjacency relationships while maintaining storage space within reasonable limits. The data structure effectiveness is demonstrated by two different applications: for supporting fragmentation simulation and for supporting volume rendering algorithms.

Original languageEnglish (US)
Pages (from-to)1529-1556
Number of pages28
JournalInternational Journal for Numerical Methods in Engineering
Issue number11
StatePublished - Nov 21 2005


  • Finite element mesh
  • Implicit entities
  • Reduced representation
  • Topological data structure

ASJC Scopus subject areas

  • Numerical Analysis
  • Engineering(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A compact adjacency-based topological data structure for finite element mesh representation'. Together they form a unique fingerprint.

Cite this