plugin.php

<?php
class Some_Plugin {
	function previous_gallery_post_link() {

		add_filter( 'posts_where', array( &$this, 'filter_where_date_lt' ) );
		$previous = new WP_Query( array(
			'post_type' => 'post',
			'tax_query' => array(
				'relation' => 'AND',
				array(
					'taxonomy' => 'post_format',
					'field' => 'slug',
					'terms' => array( 'post-format-gallery' )
				)
			),
			'order' => 'DESC',
			'posts_per_page' => 1
		) );

		// Clean filters
		remove_filter( 'posts_where', array( &$this, 'filter_where_date_lt' ) );
	
		if ( $previous->have_posts() ) {
			$previous->the_post();
			echo '<a class="previous" href="' . get_permalink() . '">Previous</a>';
		}
	
		wp_reset_postdata();
	}

	function next_gallery_post_link() {
	
		add_filter( 'posts_where', array( &$this, 'filter_where_date_gt' ) );
		$next = new WP_Query( array(
			'post_type' => 'post',
			'tax_query' => array(
				'relation' => 'AND',
				array(
					'taxonomy' => 'post_format',
					'field' => 'slug',
					'terms' => array( 'post-format-gallery' )
				)
			),
			'order' => 'ASC',
			'posts_per_page' => 1
		) );

		// Clean filters
		remove_filter( 'posts_where', array( &$this, 'filter_where_date_gt' ) );
	
		if ( $next->have_posts() ) {
			$next->the_post();
			echo '<a class="next" href="' . get_permalink() . '">Previous</a>';
		}
	
		wp_reset_postdata();
	
	}

	function filter_where_date_lt( $where ) {
		global $post, $wpdb;
		$where .= " AND $wpdb->posts.post_date < '{$post->post_date}' ";
		return $where;
	}

	function filter_where_date_gt( $where ) {
		global $post, $wpdb;
		$where .= " AND $wpdb->posts.post_date > '{$post->post_date}' ";
		return $where;		
	}
}
?>